(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?)

A quick brute force search shows that this will always terminate in 8 or fewer steps.

ReplyDeleteHere's a histogram of the number of steps taken for all 8 digit numbers:

0: 1 (There is a unique solution)

1: 3359

2: 1407840

3: 4939200

4: 17522400

5: 40745460

6: 25723446

7: 7367025

8: 2291268

Note that your example appears to take 12 steps, but there's an error. The sequence for 11111111 is:

11111111

10000080

30000016 (Not 30000006)

41001015

40110033

40012023

50011213

50101132

This problem reminds me of the Collatz conjecture. Either it's true that all numbers converge to a working answer, or there exists some input that is part of a loop.

For some smaller number of digits, you do get loops. For example, if you use 2 digits of the form d_7 d_0, there is a loop 00 -> 12 -> 20 -> 21 -> 20. Three, four, five and seven digit sequences also have loops.

Interestingly, at 6 digits, there are no loops and two solutions: 411031 and 410221.