Back
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.
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... :-)
Does anyone else work on this problem?
Tommorow I will post one hint that may help with the proof part.
I got a solution. Not by trial and error :-/
I have a constructing proof that there is only one solution.
I also have a "constructive" proof that there is only one solution. If
there is a nicer proof, I would like to see it. :-)
Hmmm. I'm ashamed: I'll have to think it over.
(BTW: One say "constructive"? thx.)
> (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". ;-)
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.
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
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.
:)
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
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.
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. :)
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.
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. :)
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
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.
> 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?)
> 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.
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
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
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.