Author: migo (Mikhael Goikhman)
Date: 2003-Nov-13 12:35:04

This is an easy puzzle. I solved the first part in 3 minutes, so I invented
the second part to make it more interesting. You are, of course, not
limited in time.

(1). This number has 10 digits. The first digit is how many '1's this 
number has, the second digit is how many '2's this number has and so on,
the 10-th digit is how many '0's this number has. Find this number.

Hint/clarification: you may change the puzzle and find the number the first
digit of which means the number of zeros, and so on, the 10-th digit means
the number of '9's. You should get the same answer just rotated in 1 digit.

For the sake of completeness, the number may start with zero if needed.

(2). Optionally, prove there is only one solution.

Please do not post the solution before 16 November 2003.


Author: bandsmer (Michael Bandsmer) Date: 2003-Nov-13 18:28:38 I've found a solution to your problem by trial and error. Finding a proof that it's the only solution may take a bit longer though... :-)
Author: migo (Mikhael Goikhman) Date: 2003-Nov-14 00:37:19 Does anyone else work on this problem? Tommorow I will post one hint that may help with the proof part.
Author: dudzus (Heiko Dudzus) Date: 2003-Nov-14 09:15:07 I got a solution. Not by trial and error :-/ I have a constructing proof that there is only one solution.
Author: jason (Jason Jordan) Date: 2003-Nov-14 09:22:11 I also have a "constructive" proof that there is only one solution. If there is a nicer proof, I would like to see it. :-)
Author: dudzus (Heiko Dudzus) Date: 2003-Nov-14 09:44:16 Hmmm. I'm ashamed: I'll have to think it over. (BTW: One say "constructive"? thx.)
Author: jason (Jason Jordan) Date: 2003-Nov-14 09:58:03 > (BTW: One say "constructive"? thx.) I just mean that it's not so much a constructive proof as it is an exhaustive search of the solution space. Brute force, while a valid method of proof, is not very elegant. That's why I put quotes around the word "constructive". ;-)
Author: migo (Mikhael Goikhman) Date: 2003-Nov-14 14:23:45 My proof is not very compact/constructive/formal either. But it's correct. I know for sure it takes me less characters/time to write a script searching for all solutions than to formalize the proof. :) A hint that may help to start with a proof is: Think what should be the sum of digits in the requested number.
Author: tomc (Tom Carmichael) Date: 2003-Nov-14 17:06:13 I guess I've also been looking something 'formal' in the proof. An enumeration of cases is legit, but tedious. :-) It's certainly possible to show via proof by contradiction some numbers which cannot be in the final solution, but I'm not far enough down those roads to show that the solution is unique. Back to the drawing board... Tom
Author: dudzus (Heiko Dudzus) Date: 2003-Nov-14 19:01:02 Yes, I've finally found a proof. Constructive at the end, kind of formal trial and error in the middle. As mathematician I can't stop searching for a neat formal way to prove it. :)
Author: bandsmer (Michael Bandsmer) Date: 2003-Nov-15 00:22:09 I've finally found some time to put together a nice clean proof that constructs the solution and proves it is unique. (And it's not a brute force search.) I'll post the proof sometime after Nov 16. Mike
Author: migo (Mikhael Goikhman) Date: 2003-Nov-15 02:08:43 I will not post any more hints, but the following entertaining info may be used as a hint or as a new challenge. As I expected, writting a script was an easy and quick task, so now I have some generic results. If we take a number consisting of N digits (including systems with the base greater than 10) then the number of solutions is: N=1 no solutions N=2 no solutions N=3 no solutions N=4 2 solutions N=5 1 solution N=6 no solutions N=7 1 solution N=8 1 solution N=9 1 solution N=10 1 solution <- this is what you should find N=11 1 solution N=12 1 solution All solutions with N>=7 are basically the same solution, so if you only want to find a solution for N=10, it is probably easier to do it for N=7 or N=8. :) Try to solve the task for N=4 and N=5 too, should be easy.
Author: migo (Mikhael Goikhman) Date: 2003-Nov-16 12:47:53 In this message I will use the puzzle variant that starts with 0, not 1. The required number is 6210001000 (or 2100010006 in the original rules). Solutions for other N: N=4 1210, 2020 N=5 21200 N>7 3211000, 42101000, 521001000, 6210001000, 72100001000... The proof that there is only one solution for N=10 goes like this. The sum of digits in our number should be 10. So look into all numbers the first digits of which is 0, then 1, then 2 until 9. The meaning is the number should include no zeros, one zero, two zeros .. 9 zeros. There are no many cases, so you may complete the proof yourself. :) I do have the complete formal prove, but I prefer to see the other works. There is another way to prove there is only one solution, my script. :) You may access it at ~migo/math/scripts/SelfDescribingNumber . There are two more scripts in this directory that solve problems of expressing of N cents using M coins and solving Egyptian fractions. Depending on the input, all 3 scripts may run either seconds or minutes or hours, so if you want to experiment with them, please use your home machine, do not load freeshell.org. :)
Author: dudzus (Heiko Dudzus) Date: 2003-Nov-16 18:37:57 You can read my proof on http://dudzus.unixcab.org/stuff/self_describing_number.pdf or gopher://sdf.lonestar.org/11/users/dudzus/stuff/self_describing_number.pdf Sorry for my poor mathematical english. I tried to transfer the problem into "linear algebra" but failed.
Author: migo (Mikhael Goikhman) Date: 2003-Nov-16 20:33:26 Very nice work, dudzus! :) I didn't check the entire proof, but it seem to be ok. I can see some minor typos and gaps. For example, in Claim 1, "if it was x0 <= 6" should be "if it was x0 < 6". Now, it is not immediatelly clear why "there still have to be at least 3 other digits nonzero", you only show this in the next claim 2 and case 1. It is also not immediatelly clear how the second equation S{i = 0..9}(i * xi) = 10 follows the definition. :) I think the proof of Michael is similar. It is even possible he will proof read your work better than me. :)
Author: dudzus (Heiko Dudzus) Date: 2003-Nov-16 21:39:01 migo wrote: > For example, in Claim 1, "if it was x0 <= 6" should be > "if it was x0 < 6". You are right. > Now, it is not immediatelly clear why "there still have to be at least > 3 other digits nonzero", you only show this in the next claim 2 and > case 1. I think it's consecutive: In proof for claim 1 I am searching a lower threshold for the sum in equation (4). If x0 < 6, there are at most 5 zero-digits. Hence there are at least 5 non-zero digits. Perhaps two of them aren't counted in the sum of equation (4); but at least three of them are so. This gives the lower threshold of 9. I can't see a gap. Thx and regards, Heiko
Author: migo (Mikhael Goikhman) Date: 2003-Nov-16 22:51:11 dudzus: yes, the claim 1 is consecutive. I saw a minor gap here, because you arbitrary take the first 5 digits to be non-zero and use the equation without x1 used; probably adding a case with x1 = 0 would look more complete, but I agree, this is intuitive as is. And what about the second equation, i.e. sum of i * xi equals 10, is it supposed to be intuitive? This equation is the key for such short proof.
Author: dudzus (Heiko Dudzus) Date: 2003-Nov-16 23:12:54 > And what about the second equation, i.e. sum of i * xi equals 10, is it > supposed to be intuitive? This equation is the key for such short proof. Hehe. Right. It is the key. Well, it is hard for me to find the words to explain. Let me try: x1 tells how often 1 appears. So the "1"s contribute 1*x1 to the cross sum. x2 tells how often 2 appears. So the "2"s contribute 2*x2 to the cross sum. x3 tells how often 3 appears. The "3"s contribute 3*x3 to the cross sum. ..... I hope this makes it clear enoug why the ckecksum can be calculated through sum(i*xi)? But you are right. This was essential. BTW. Do you allow me to fix the "x0 < 6" typo (for better understanding?)
Author: migo (Mikhael Goikhman) Date: 2003-Nov-17 00:08:10 > BTW. Do you allow me to fix the "x0 < 6" typo (for better understanding?) This is your file, you don't need to ask me to edit what you need.
Author: tomc (Tom Carmichael) Date: 2003-Nov-17 15:09:26 An interesting thing about this puzzle that I noticed for the n=10 case that seems to be true for the other cases listed as well. If a_i = # of 'i's appearing in the number, it's easy to see (as mico pointed out) that n sum (a_i) = n i What is more interesting is this also appears to be true: n sum (i * a_i) = n i For the n=10 example, we have 6*0, 2*1, 1*2 and 1*6, the sum of which is indeed 10. Anyone want to tackle a proof as to why? I haven't had much time to look into it, but I think it might be key to a general proof of the puzzle. Regards, Tom
Author: bandsmer (Michael Bandsmer) Date: 2003-Nov-17 18:12:29 I think dudzus' solution (with the aforementioned corrections and clarifications) is essentially complete. I arrived at the solution in a similar manner for x0 <=5, using the "cross sum" which I briefly derive below. The other cases I eliminated one by one without using the "cross sum". Here are the details: Let S be the solution, represented by the digits 'abcdefghij', i.e. a = number of 0's b = number of 1's c = number of 2's ... j = number of 9's S has 10 digits, so [1] a + b + c + d + e + f + g + h + i + j = 10 Now we step through a few basic cases: CASE 1: a=9? This is impossible. All other digits b...j would have to be 0 in order for us to have 9 zeroes, and this obviously isn't a solution. CASE 2: a=8? With 8 zeroes and a=8, only one other digit can be non-zero. To satisfy [1], this digit must = 2, so we must have c = # of 2's = 1---but this is a contradiction. CASE 3: a=7? With 7 zeroes and a=7, only 2 other digits can be non-zero. To satisfy [1], one digit must be a 1 (so b = # of 1's = 1), and another must be a 2 (so c = # of 2's = 1)---but this is another contradiction since neither of these digits is = 2. CASE 4: a=6? Exactly 3 other digits are non-zero. To satisfy [1], two of them must be 1's (so b=2), and one of them must be a 2 (so c=1). The other non-zero digit must be g=1 (because the number of 6's is 1). THIS IS A SOLUTION: 'abcdefghija' = 6210001000 CASE 5: a<=5? We know that there are "a" 0's, "b" 1's, "c" 2's, ..., "j" 9's; thus, the sum of the digits is given by b + 2c + 3d + 4e + 5f + 6g + 7h + 8i +9j. But notice that [1] also gives the sum of the digits, so, equating this expression with [1], we have [2] b + 2c + 3d + 4e + 5f + 6g + 7h + 8i +9j = 10 Now, getting back to our case where a <= 5, we must have 4 or more non-zero digits in b,c,...j. From [2], the only possible solution is to use the smallest digits, i.e. b=c=d=e=1. But you can quickly check that this isn't a solution. Thus, the solution 'abcdefghij' = 6210001000 is the only solution. Michael
Author: migo (Mikhael Goikhman) Date: 2003-Nov-17 18:56:47 My own proof is very similar to the Michael's one. I have the same cases but a more intuitive than a formal explanation for small values of the first digit. The intuitive explanation is indead based on this formal equation sum(i * x_i) = 10, but instead of immediately coming to a contradiction some possible sub-cases are examined. The Michael's solution is pretty compact, although it is still 2.5 times more verbose than my script without comments. :-) Thank all for participation. A time to think about a new puzzle.