(June 29th, co-located with STOC, will be a workshop to celebrate Vijay Vazarani's 60th birthday. As computer scientists shouldn't we use 64 as the milestone? See here for details about the workshop, not about 60 vs 64.)
I will likely post a lot about Gathering For Gardner 13, but for now I will just give one problem I saw there. I will not say the speaker or the title of the talk as that might be a clue. I'll give the answer in my next post which will be this week
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
You could prob find such a number by computer search- but don't.
Feel free to comment. I will not block comments (except those we usually block- usually spam) but by the same token, if you don't want hints, don't read the comments.
I've started from evaluating d_7. It is obviously >1, since if it is 1, the only possible number is 11111111 which is not good. On the other hand, since sum of d_i from 0 to 6 is 8, d_7<=5 (0+1+2+3+4>8). Also, d_6=0, since else we'll need to repeat some number 6 times (as d_7!=6).
ReplyDeleted_7=2 felt too low. I tried d_7=3. Playing around with it, I got the feeling that even if I manage to put the numbers, I'll use all of 0,1,2 thus violating d_7 rule. For d_7=4 I found something close to the answer pretty fast:
40______ -> 40_1____
d_5 got to be 0:
40_1____ -> 4001____
Putting 2 into d_0 and thus 1 into d_2:
4001____ -> 4001_1_2
Now we can put d_1=3 and d_3=1, acquiring
4001_1_2 -> 40011132
The problem is, I've used 0,1,2,3,4 which means d_7=5. Luckily, it can be fixed easily
50101132
I found a solution by hand search branching first on d_7, then on the position for the value in d_7. Not sure how the name of the person who posed the problem would serve as a clue
ReplyDelete00000000
ReplyDelete10000008
30000016
41001015
40110033
40012023
50011213
50101132
50101132
50101132
...
Nice. It seems to converge for any starting choice.
DeleteNote that for the 8-digit number the solution is unique; for larger bases e.g. 16-digit hex numbers, we can have multiple solutions:
ReplyDelete500001000010022A
500001000010103A
... but all with 5 distinct digits.
Clearly I didn't spend the whole night checking it, but used a 5 minute minizinc program :-)
include "globals.mzn";
array [0..15] of var int : num;
constraint count_eq( num, 0, num[0] );
constraint count_eq( num, 1, num[1] );
constraint count_eq( num, 2, num[2] );
constraint count_eq( num, 3, num[3] );
constraint count_eq( num, 4, num[4] );
constraint count_eq( num, 5, num[5] );
constraint count_eq( num, 6, num[6] );
constraint count_eq( num, 7, num[7] );
constraint count_eq( num, 8, num[8] );
constraint count_eq( num, 9, num[9] );
constraint count_eq( num, 10, num[10] );
constraint count_eq( num, 11, num[11] );
constraint count_eq( num, 12, num[12] );
constraint count_eq( num, 13, num[13] );
constraint count_eq( num, 14, num[14] );
constraint nvalue( num[15], num );
%constraint num[1] != 2; <<
%constraint num[15] != 5;
solve satisfy;
... other nice questions could be:
Delete- is there a fast algorithm to calculate a solution on a number in base B ?
- what happens if there are more digits than the base used?
- what is the complexity of finding if there is a solution on a given number in which some digits are already specified ...
First we exclude possibility of digit above 6, meaning d_0+...+d_6=8. Then for each value of d_7, we're distributing 8 tokens into d_7 (if d_7 appears more than once) or d_7-1 (if d_7 appears once) identical bins, which aren't too many. Each way of distribution gives the digits modulo permutation. Then permutation is obtained by definition and can be verified in O(8).
ReplyDeleteExample, for d_7=3 once distribution is 3 3 2, i.e. digits are 3 3 3 2 0 0 0 0. By definition they should be permuted to 3 0 0 0 3 1 0 4, contradiction.
d_7 < 3 or d_7 > 6 could be quickly excluded.
I got the answer by guessing. Never thought about the convergence approach. Can someone explain why d_0+...+d_6=8?
ReplyDeleteD'oh! Never mind my comment.
ReplyDelete