Author |
Topic: Symmetrical Counting (Read 1304 times) |
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 2084
|
 |
Symmetrical Counting
« on: Jan 8th, 2007, 7:00am » |
 Quote  Modify
|
Inspired by my drive into work this morning:
A certain car has a 6-digit odometer, where the digits are equally spaced and each digit is an identical 7-segment display using the standard forms. Each digit, considered separately, has three symmetries (in two dimensions): two mirror axes and one 180-degree rotation. Considering only the illuminated segments; if the odometer displays the number zero as a single digit, numbers below 100000 without leading zeros, and the six least-significant digits of all higher numbers, how many of the possible unique display configurations have no overall symmetry? How many total overall symmetries are there (i.e. what is the sum of the number of overall symmetries of each possible display configuration)?
--SMQ
|
| « Last Edit: Jan 8th, 2007, 7:03am by SMQ » |
 IP Logged |
--SMQ
|
|
|
balakrishnan
Junior Member
Gender:
Posts: 92
|
|
Re: Symmetrical Counting
« Reply #1 on: Jan 8th, 2007, 9:07am » |
Quote Modify
|
Edited solution below
|
| « Last Edit: Jan 8th, 2007, 4:23pm by balakrishnan » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
By "overall symmetry" I mean a symmetry of the display taken as a whole; so the display of the number "123" has no overall symmetries, the display of the number "138" has one (a vertical mirror symmetry), and the display of the number "808" has three: a horizontal mirror symmetry, a vertical mirror symmetry, and a 180-degree rotational symmetry. Your assumption was essentially correct, but could lead you to miss some of the more subtle cases. 
I've attached a diagram of the display of the digit "8", just in case anyone was still unsure of my description -- note that the individual segments are themselves three-way symmetrical as well.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
balakrishnan
Junior Member
Gender:
Posts: 92
|
|
Re: Symmetrical Counting
« Reply #3 on: Jan 8th, 2007, 4:22pm » |
Quote Modify
|
The question is totally different then!
First let us compute the number of numbers that have 3 symmetries:
In that case only those numbers will have 3 symmetries that are both symmetrical as a number(palindrome) and consists only of 0s and 8s
If you are talking of numbers from 0 to (10^k)-1
for m digits,the number of palindromes formed of 0s and 8s are(first and last digit mustbe 8 since it is a m-digit number)
for the remaining m-2 digits:
If m is even,then (m-2)/2 free parameters that can be formed from 0's or 8's
So we have 2^{(m-2)/2} such m-digit numbers
If m is odd,there are (m-1)/2 free parameters
which means 2^{(m-1)/2} variables
So the number of k-digit numbers that have 3 symmetries are
1+2^(0)+2^(0)+2^(1)+2^(1)+...
if k is even,it is clear that the sum is simply
2^{(k+2)/2}-1
If k is odd,it is clear that the sum is simply
2^{(k+3)/2}-2^{(k-1)/2-1
Now let us compute the numbers that have 2-way symmetry:
this can be easily shown to be zero for all k
Now let us go to 1-way symmetry:
Let us compute those numbers that have one-way symmetry along the right reflection.
note that only 0,2,5,8 are the numbers that on right reflection gives a valid number
For every m digit number,we have a right way-symmetry,only if the right reflection of the number gives the same number.
as always first digit has to be 2,5,8(as it cannot be zero).Once the first digit is fixed,the last digit is automatically fixed(for 2,5,8 it is 5,2,8 respectively).
for the remaining (m-2) digits,
If m-2 is even,we would have 4^{(m-2)/2} numbers
If m-2 is odd,we would have 2*4^{(m-3)/2} numbers
because the central number has to be 0,8
So for every m-digit,the number of numbers that have 1-way right symmetry are
If m is even
3*4^{(m-2)/2}
If m is odd
6*4^{(m-3)/2}
and 1 for m=1
Now let us compute the number of numbers that have 1-way down symmetry.
This can happen if and only if each number is vertically symmetric which are 0,1,3,8
Automatically the first number is either of 1,3,8
The next m-1 numbers are selected in 4^(m-1) ways
and hence a total of 3*4^(m-1) ways
Now for rotationally symmetric numbers(the only rotationally symmetric numbers are 0,2,5,6,8,9).
The first digit should be again 2,5,6,8,9(5 ways)
The last digit is automatically fixed.
If m is even,there are 5.6^{(m-2)/2}
If m is odd ,there are 4*5.6^{(m-3)/2} numbers for m>1.If m=1,we have 4 numbers(namely 0,2,5,8 as these are the numbers that give themselves on rotation)
Noting that there are no 2-way symmetric numbers, the total number of m-digit numbers that are 1-way symmetric is
If m is even:
f_1(m)=3*4^((m-2)/2)+3*4^(m-1)+5*6^[(m-2)/2]-3*2^[(m-2)/2]
If m is odd:
f_1(m)=max(1,6*4^[(m-3)/2])+3*4^(m-1)+max(3,20*6^[(m-3)/2])-3*2^[(m-1)/2]
So for k=odd(say k=2n+1)
3*[1+4+..4^(n-1)]+1+6*[1+..4^(n-1)]+[4^k-1]+3+5*{1+..6^(n-1)}+20*{1+...6^(n-1)}-3*{1+..2^n}-3*{1+..2^(n-1)}
=10+3*(4^{(k-1)/2}-1)+[4^k-1]+5*{6^{(k-1)/2}-1}-9*2^{(k-1)/2}
If k is even(say k=2n)
3*[1+4+..4^(n-1)]+1+6*[1+..4^(n-2)]+[4^k-1]+3+5*{1+..6^(n-1)}+20*{1+..6^(n-2)}-6*{1+..+2^(n-1)}
=3[4^n-1] +1-6*4^(n-1)+4^k-1+3+5*{6^n-1}-20*6^(n-1)-6[2^n-1]
|
|
IP Logged |
|
|
|
balakrishnan
Junior Member
Gender:
Posts: 92
|
|
Re: Symmetrical Counting
« Reply #4 on: Jan 8th, 2007, 4:22pm » |
Quote Modify
|
Summarizing:
the number of numbers that are 1-way symmetric from 0 to 10^k-1
Uni(k)=
=1+3*2^(k-1)+4^k+5*6^((k-1)/2)-9*2^((k-1)/2)..If k is odd
=1+3*2^(k-1)+4^k+5/3*6^(k/2)-6*2^(k/2)..If k is even
the number of numbers that are 2-way symmetric from 0 to 10^k-1
Bi(k)=
0..for every k
the number of numbers that are 3-way symmetric from 0 to 10^k-1
Tri(k)=
3*2^((k-1)/2)-1..if k is odd
2^(1+k/2)-1..if k is even
Number of numbers that have no symmetry from 0 to 10^k-1
Z(k)=
10^k-3*2^(k-1)-4^k-5*6^((k-1)/2)+6*2^((k-1)/2)..if k is odd
10^k-3*2^(k-1)-4^k-5/3*6^(k/2)+2^(2+k/2)..if k is even
Total symmetry for 0 to 10^k-1
T(k)=
-2+3*2^(k-1)+4^k+5*6^((k-1)/2)..if k is odd
-2+3*2^(k-1)+4^k+5/3*6^(k/2)..if k is even
Answer to your first question is Z(5)=98772(in this we consider all numbers from 0 to 99999)
If you are looking for Z(6) it is 995480(in this we consider all numbers from 0 to 999999)
Answer to your second question is T(5)=1250(numbers from 0 to 99999)
If you are looking for T(6) it is 4550(numbers from 0 to 999999)
|
| « Last Edit: Jan 8th, 2007, 4:26pm by balakrishnan » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Symmetrical Counting
« Reply #5 on: Jan 8th, 2007, 4:56pm » |
Quote Modify
|
Your analysis is correct as far as it goes, but you are missing a few possibilities.
Hint 1: Given the way I described how the odometer displays numbers, how many possible unique readouts are there (assuming the car runs long enough, of course)?
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
balakrishnan
Junior Member
Gender:
Posts: 92
|
|
Re: Symmetrical Counting
« Reply #6 on: Jan 8th, 2007, 5:03pm » |
Quote Modify
|
If you think my answer is wrong
your question is just not clear!
The number of unique numbers on a k-digit odometer is 10^k
PS:I have checked the answers using a computer program
|
| « Last Edit: Jan 8th, 2007, 5:08pm by balakrishnan » |
IP Logged |
|
|
|
balakrishnan
Junior Member
Gender:
Posts: 92
|
|
Re: Symmetrical Counting
« Reply #7 on: Jan 8th, 2007, 5:16pm » |
Quote Modify
|
ex:
For numbers from 0 to 99,the numbers that are 1-way symmetric are
1,2,3,5,10,11,13,18,22,25,30,31,33,38,52,55,69,80,81,83,96
which is a total of 21 numbers and my formula gives the same answer
1+3*2^(k-1)+4^k+5/3*6^(k/2)-6*2^(k/2)=21 for k=2
Similarly for other cases and higher ks
|
|
IP Logged |
|
|
|
balakrishnan
Junior Member
Gender:
Posts: 92
|
|
Re: Symmetrical Counting
« Reply #8 on: Jan 8th, 2007, 7:16pm » |
Quote Modify
|
Given that you have not mentioned what "unique display configuration" means,my answer is correct as it stands!
|
| « Last Edit: Jan 8th, 2007, 7:17pm by balakrishnan » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Symmetrical Counting
« Reply #9 on: Jan 8th, 2007, 7:32pm » |
Quote Modify
|
on Jan 8th, 2007, 7:16pm, balakrishnan wrote:| Given that you have not mentioned what "unique display configuration" means,my answer is correct as it stands! |
|
Touchy, touchy.
I'm sorry if you feel I'm not being clear -- your analysis is exemplary as far as it goes -- but I think you need to read a bit closer. Hint 2: Given that "the odometer displays the number zero as a single digit, numbers below 100000 without leading zeros, and the six least-significant digits of all higher numbers", how would the odometer display 1,000,000?
Also, that is not the only nuance I believe you are missing. Obviously it's simplest for me since I posed the riddle and know what I was thinking, but I chose to post it at the medium difficulty level for good reasons.
You've done an excellent job with the "easy" portion of the riddle, now look to see what you may have overlooked.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
balakrishnan
Junior Member
Gender:
Posts: 92
|
|
Re: Symmetrical Counting
« Reply #10 on: Jan 8th, 2007, 8:49pm » |
Quote Modify
|
Now all I need to do is to add the number of numbers from 000000 to 099999 that have no symmetry
Let us first compute the numbers that have 3-way symmetry for 00(k zeros) to 0(k-1 9s)
Clearly for 3way symmetry if the first digit is 0,last digit has to be zero.So for the remaining k-2 digits,we would have to put either 0 or 8
which is a total of 2^[(k-1)/2] where [.] is the floor function
2^((k-2)/2)..if k is even
2^((k-1)/2)..if k is odd
Computing the number of 2-way symmetry if the first digit is 0
This is 0
Computing the number of 1-way symmetry if the first digit is 0
--First for the right-reflection symmetry.
On similar analysis as previous post,we get
If k is even,we would have 4^{(k-2)/2} numbers
If k is odd,we would have 2*4^{(k-3)/2} numbers
--Now for the down-reflection
there are 4^(k-1)
--Now for the rotation part
If k is even,there are 6^{(k-2)/2}
If k is odd ,there are 4*6^{(k-3)/2}
Summarizing:
Number of 1-way symmetries for numbers from 000(k times) to 0(k 9s)
Uni_h(k)=
4^(k-1)+2^(k-2)+6^((k-2)/2)-3*2^((k-2)/2)..if k is even
2*4^((k-3)/2)+4^(k-1)+4*6^((k-3)/2)-3*2^((k-1)/2)..if k is odd
Number of 2-way symmetries for numbers from 000(k times) to 0(k 9s)
Bi_h(k)=
0..for every k
Number of 3-way symmetries for numbers from 000(k times) to 0(k 9s)
Tri_h(k)=
2^((k-2)/2)..if k is even
2^((k-1)/2)..if k is odd
Number of numbers that have no symmetries for numbers from 000(k times) to 0(k 9s)
Z_h(k)=
10^(k-1)-4^(k-1)-2^(k-2)-6^((k-2)/2)+2^(k/2)..if k is even
10^(k-1)-2^(k-2)-4^(k-1)-4*6^((k-3)/2)+2^((k+1)/2)..if k is odd
Number of total-symmetries for numbers from 000(k times) to 0(k 9s)
T_h(k)=
4^(k-1)+2^(k-2)+6^((k-2)/2)..if k is even
2*4^((k-3)/2)+4^(k-1)+4*6^((k-3)/2)..if k is odd
Z_h(6)=98932
Z(6)=995480
So the intended answer for the first part is Z_h(6)+Z(6)=1094412
T_h(6)=1076
T(6)=4550..(already said before)
So total number of symmetries(answer to the second part)=1076+4550=5626
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Symmetrical Counting
« Reply #11 on: Jan 9th, 2007, 5:44am » |
Quote Modify
|
Again, excellent work ... as far as it goes. You're now 99% of the was there, but I believe there's still a slight adjustment to be made to the answer to the second part.
Hint 3: Your answer and mine for the second part differ by exactly twelve.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
balakrishnan
Junior Member
Gender:
Posts: 92
|
|
Re: Symmetrical Counting
« Reply #12 on: Jan 9th, 2007, 7:19am » |
Quote Modify
|
I am not sure what I am missing.
If the answer to the first part is 1094412, then I think the answer to the second part is correct.
I have also verified it using a computer program(matlab code).
I just counted the number of numbers that have k-way symmetry from 0 to 1099999 which is N(k)
and then did N(1)+2*N(2)+3*N(3) and got the same answer viz 5626
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Symmetrical Counting
« Reply #13 on: Jan 10th, 2007, 6:42am » |
Quote Modify
|
Well, since nobody else seems to be playing...
Hint 4: There is a small set of display configurations for which the phrase "considering only the illuminated segments" is important in correctly counting the number of overall symmetries.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
balakrishnan
Junior Member
Gender:
Posts: 92
|
|
Re: Symmetrical Counting
« Reply #14 on: Jan 10th, 2007, 7:47am » |
Quote Modify
|
That is too subtle .
you mean 1,11,111,1111,11111,111111 will have 3 symmetries (while I considered only 1).
So the answer for total symmetries would be added by 12 and hence the answer is 5626+12=5638
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print