Thursday, January 7, 2016

The Self-Referential Number

Recently, singingbanana (who goes by @jamesgrime on twitter) actually managed to post a video.  In this case, it was a puzzle.  The quest is to find a self-referential number, defined as a 10-digit number (implied to be in base 10) where the 1st digit says how many digits in the number are '0', the 2nd digit says how many digits in the number are '1', and so on.
You might want to try this problem yourself, so consider this your spoiler warning.  
Spoilers follow.
































The answer that I found was 6,210,001,000.  I suspect that this is the only solution, but I haven't proven that yet.  Maybe later.
I defined each digit with a letter, such that the number will be a,bcd,efg,hij.  Since the number has 10 digits, a+b+c+d+e+f+g+h+i+j=10.
Then, I put limits on how high each digit could be, just using itself and how many of its thing it represents.  For instance, a<=10 (even though 10's not a digit), because 10+10*0<=10.  Similarly, b<=5 because 5+5*1<=10, and c<=3 because 3+3*2<=10.
a<=9
b<=5
c<=3
d<=2
e<=2
f<=1
g<=1
h<=1
i<=1
j<=1
Basically, there can't be more than 1 of anything that counts 5s or larger, because having 2 of the thing that it counts (I probably should have come up with symbology for that) would be at least 10, and adding the counter then exceeds 10.
This also applies to the collection, though, so f+g+h+i+j<=1.
This also means that there are at least 4 0s, so 4<=a<=9.
If e=1, then e+4=5, so that would also force f through j to be 0.  Thus, e+f+g+h+i+j<=1.
This means that there are at least 5 0s, so 5<=a<=9.
Since a>4, it follows that some member of {f,g,h,i,j} is at least 1, and thus exactly 1.  This also means that e=0, so there are no 4s in this number.
Since there's at least one 1, b>=1.
If b were to be 1, though, then there would be at least two 1s, forcing b to be at least 2.  This would cause a problem for b, but wait, there's a 2, so c>=1.
Suppose that c=1 and b=2.  Using X as a placeholder for a, the number looks like this:
X,21?,0[01][01],[01][01][01]
where only 1 of those [01]s is actually a 1, and the rest 0.  
I don't see any 3s, so suppose that d=3.  We now know that there are 6 0s.  Thus, a=6.
Since there's one 6, g=1.  This gives us:
6,210,001,000

QED

P.S.:  The writing on this is a bit sloppy, but I'm using  plain text and I'm in a hurry.  I might edit this later for formality. 

UPDATE 2016/Jan/13:  So, the morning after I posted this (so the 8th), I thought of a proof that a<7.  And now I have a spare moment!  :D 

Assume that a > 6.  Then, hij=001, 010, or 100.  Then, b>0.
b=1 and (h=1 xor i=1 xor j=1) ==> b>1 ==> c>0 or d>0.  (See above that e+f+g+h+i+j <=1.) 
Since a≠0, b≠0, c≠0, and 1 of h, 1, or j ≠0, there are at least 4 non-0 digits, so there are no more than six 0 digits.  Thus, a, the number of 0 digits, cannot exceed 6.  

QED

No comments: