 # 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: