The 8 digit number I asked for

(On June 29th, co-located with STOC, there will be a workshop to celebrate Vijay Vazarani's 60th birthday. See here. As computer scientists shouldn't we use 64 as the milestone?)



At Gathering for Gardner 13 Peter Winkler gave a great talk entitled

Problems that Solve Themselves.

(The title kind-of gives away how to solve it. And its just the kind of thing Peter Winkler would talk about. Hence I omitted the title and author when I first posted about it)

I blogged about one of them, asking for the answer. I repeat the problem and answer it:

Find an 8-digit number

d_7 d_6 d_5 d_4 d_3 d_2 d_1 d_0

such that

d_0 is the number of 0's in the number

d_1 is the number of 1's in the number

d_2 is the number of 2's in the number

.....

d_6 is the number of 6's in the number

but

d_7 is NOT necc the number of 7's

d_7 is the number of DISTINCT DIGITS in d_7 d_6 d_5 d_4 d_3 d_2 d_1 d_0

WRONG APPROACH: Work out algebra for the digits, try to force it Actually, I had thought this was the wrong approach but some of the comments on my last blog DID do this.

RIGHT APPROACH:  Take an aribtrary number like

1 1 1 1 1 1 1 1

NOW- look at it and count the number of 0's, 1's, ... 6'ls and the number of distinct numbers
For the new number let

d_0 be the number of 0's in the old number

....

d_6 be the number of 6's in the old number

d_7 be the number of distinct digits

To get

1 0 0 0 0 0 8 0

iterate the process to get

3 0 0 0 0 0 0 6

3 1 0 0 0 0 0 6

4 1 0 0 1 0 1 5

4 0 1 1 0 0 2 3

5 0 0 1 1 1 2 2

4 0 1 0 0 2 3 2

5 0 0 1 1 2 1 2

4 0 1 0 0 2 3 2

5 0 0 1 1 2 1 3

5 0 1 0 1 1 3 2

5 0 1 0 1 1 3 2

AH- this number works!

Peter Winkle claims that if you start with any 8 digits number this process will converge to a solution within at most 15 steps. I do not think he proved this. But the key here is that by NOT being clever you can easily find the answer. The problem, as the title of the talk says, solves itself!

How many such numbers are there? Proving the process works? Getting statistics on how long it will take on average? I leave all of this to the reader. (I do not know the answers.) And one can ask all of this for other bases and other condidtions on the digits (though calling them digits is odd since that smacks of base 10- what to use instead of ``digits'' when in another base?)