343 logic/self.ref.p
Description
This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.
343 logic/self.ref.p
Find a number ABCDEFGHIJ such that A is the count of how many 0's are in the
number, B is the number of 1's, and so on.
logic/self.ref.s
6210001000
For other numbers of digits:
n=1: no sequence possible n=2: no sequence possible n=3: no sequence possible n=4: 1210, 2020 n=5: 21200 n=6: no sequence possible n=7: 3211000 n=8: 42101000 n=9: 521001000 n=10: 6210001000 n>10: (n-4), 2, 1, 0 * (n-7), 1, 0, 0, 0
No 1, 2, or 3 digit numbers are possible. Letting x_i be the ith
digit, starting with 0, we see that (1) x_0 + ... + x_n = n+1 and
(2) 0*x_0 + ... + n*x_n = n+1, where n+1 is the number of digits.
I'll first prove that x_0 > n-3 if n>4. Assume not, then this
implies that at least four of the x_i with i>0 are non-zero. But
then we would have \sum_i i*x_i >= 10 by (2), impossible unless n=9,
but it isn't possible in this case (51111100000 isn't valid).
Now I'll prove that x_0 < n-1. x_0 clearly can't equal n; assume
x_0 = n-1 ==> x_{n-1} = 1 by (2) if n>3. Now only one of the
remaining x_i may be non-zero, and we must have that x_0 + ... + x_n
= n+1, but since x_0 + x_{n-1} = n ==> the remaining x_i = 1 ==> by
(2) that x_2 = 1. But this can't be, since x_{n-1} = 1 ==> x_1>0.
Now assuming x_0 = n-2 we conclude that x_{n-2} = 1 by (2) if n>5
==> x_1 + ... + x_{n-3} + x_{n-1} + x_n = 2 and 1*x_1 + ... +
(n-3)*x_{n-3} + (n-1)*x_{n-1} + n*x_n = 3 ==> x_1=1 and x_2=1,
contradiction.
Case n>5:
We have that x_0 = n-3 and if n>=7 ==> x_{n-3}=1 ==> x_1=2 and
x_2=1 by (1) and (2). For the case n=6 we see that x_{n-3}=2
leads to an easy contradiction, and we get the same result. The
cases n=4,5 are easy enough to handle, and lead to the two solutions
above.
--
-- clong@romulus.rutgers.edu (Chris Long)
Continue to:
My Books
