|
||
|
Title: Symmetrical Counting Post by SMQ on Jan 8th, 2007, 7:00am 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 |
||
|
Title: Re: Symmetrical Counting Post by balakrishnan on Jan 8th, 2007, 9:07am Edited solution below |
||
|
Title: Re: Symmetrical Counting Post by SMQ on Jan 8th, 2007, 11:20am 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 |
||
|
Title: Re: Symmetrical Counting Post by balakrishnan on Jan 8th, 2007, 4:22pm 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] |
||
|
Title: Re: Symmetrical Counting Post by balakrishnan on Jan 8th, 2007, 4:22pm 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) |
||
|
Title: Re: Symmetrical Counting Post by SMQ on Jan 8th, 2007, 4:56pm 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 |
||
|
Title: Re: Symmetrical Counting Post by balakrishnan on Jan 8th, 2007, 5:03pm 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 |
||
|
Title: Re: Symmetrical Counting Post by balakrishnan on Jan 8th, 2007, 5:16pm 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 |
||
|
Title: Re: Symmetrical Counting Post by balakrishnan on Jan 8th, 2007, 7:16pm Given that you have not mentioned what "unique display configuration" means,my answer is correct as it stands! |
||
|
Title: Re: Symmetrical Counting Post by SMQ on Jan 8th, 2007, 7:32pm on 01/08/07 at 19:16:56, balakrishnan wrote:
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 |
||
|
Title: Re: Symmetrical Counting Post by balakrishnan on Jan 8th, 2007, 8:49pm 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 |
||
|
Title: Re: Symmetrical Counting Post by SMQ on Jan 9th, 2007, 5:44am 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 |
||
|
Title: Re: Symmetrical Counting Post by balakrishnan on Jan 9th, 2007, 7:19am 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 |
||
|
Title: Re: Symmetrical Counting Post by SMQ on Jan 10th, 2007, 6:42am 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 |
||
|
Title: Re: Symmetrical Counting Post by balakrishnan on Jan 10th, 2007, 7:47am 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 |
||
|
Title: Re: Symmetrical Counting Post by SMQ on Jan 10th, 2007, 8:23am Bingo As I said above, excellent work! --SMQ |
||
|
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |