Self-Referential Puzzles - Solutions

Solutions were received from Denis Borris, Kirk Bresniker, Dave Ellis, Bert Sevenhant, and Phillipe Fondanaiche. The solutions are included with the puzzle descriptions below.
Update 4/22/03: Mark Moyer pointed out there are more "answers" to the initial puzzle "How many letters are in the answer to this question?":

Eight plus five.
Exactly twenty-four letters.
Roughly twelve.
At least ten.
If you're counting letter tokens, then eighty-one, but if you're counting letter types, then eighteen.
Just one more than are in the question to this answer!

Spelling puzzles

From Philippe Fondanaiche:
Digit Puzzles (fill the blanks with digits 0-9, or possibly multi-digit numbers): From Philippe Fondanaiche:
Self-Referential Numbers
213 can be described as having "One 1, One 2, One 3", or 111213. In a successive list, with each line describing the previous, we get:
213
11 12 13
41 12 13
31 12 13 14
41 12 23 14
31 22 13 24
21 32 23 14
... and the last number (21322314) describes itself.
Update 10/3/00 - Ulrich Schimke sent several more analyses to add to the self-referential numbers:
I found your article about self referential numbers in 980608 and I have some 
facts to supplement. 
To shorten things I denote with T the describing operator for integers, so 
T(1334) = 112314, T(22) = 22 and so on. 


1) There are exactly 109 fixed-points (= self-refential numbers), i.e. n with 
T(n) = n. I examined this topic about a year ago and sent this sequence to 
Neil Sloane. They are sequence A047841, see 
http://www.research.att.com/cgi-bin/ 
access.cgi/as/njas/sequences/eisA.cgi?Anum=A047841
The reason I found your page was my search about this topic using some of 
these fixed-points as input for a search engine e.g. 21322314.     

2) You ask if the list always ends in fixed-point or a cycle. The answer is 
Yes. This is a consequence from 2 facts: A) For every n with more than 21 
digits T(n) < n is valid and B) For every n with not more than 21 digits, 
T(n) has also not more than 21 digits. As a consequence the sequence n, T(n), 
T(T(n)) ... enters and than remains in the bounded area from 1 to 10^21, so 
it must end in a cycle (see a fixed-point as a 1-cycle) 
To show A) and B) consider that T(n) has a maximum nuber of digits if the 
digits in n are distributed as equal as possible. If you have for example 
already 100 '2's in n you need another 900 '2's to "generate" a new digit in 
T(n). But if you have just 10 '2's in n you need only 90 other '2's to get a 
new digit in T(n). If n has k digits, T(n) reaches the maximum number of 
digits if eyery digit occurs at least int(k/10)-times. This leads to A) and 
B) 

3) You ask if the number of steps until a list with a certain integer as 
start can have a length > 21. The answer is the list can be abitrarly large. 
For every a(1) > 22 not ending with a zero, there is a a(2) > a(1) with 
T(a(2)) = a(1) and a(2) not ending with a zero as well. Iterating this 
process you find a sequence of numbers a(1) < a(2) < a(3) < a(4) < .. with 
T(a(2)) = a(1), T(T(a(3)) = a(1), T(T(T(a(4))) = a(1) and so on. So the 
"pre"-phase before reaching the cycle can be abitrarly large, because the 
cycle doesn't start until a(1). Finding a(2), a(3), ...  is easy: Let's start 
e.g. with a(1) = 41.  Then a(2) is of course 1111. a(3) is 11111......111111 
(the number consisting of 111 '1's). a(4) is the integer consisting of 
(10^111-1)/9 '1's and so on. 

4) I don't know if there are any terminating cycles with lengths other than 1 
or 3. One has "only" to examine all numbers smaller than 22 digits. But this 
is too much for a progam. But if you start examining all numbers beginning 
with 1 you can stop examining a number n if T(n) < n cause T(n) has already 
be checked. This reduces the nessecary run time for the program, but I think 
this is still too much.

If you find other puzzles of this sort, feel free to submit them. I'll add them when I can.

Source: Unless noted, these are original.


Mail to Ken