Self Descriptive Number Solution and Discussion

I think that is enough time pondering the puzzle. What is my number? My number is 6210001000. In fact this is the only ten digit number that obeys my rules. It fits the rules as follows. The first digit is a six and there are 6 zeroes. The second digit is a two and there are 2 ones. This continues for the entire number. There are actually many ways of solving this puzzle. I think the most popular is the trial and improvement method. This method may at first not seem too strong as you have 9 billion possibilities to try. However, many people's intuition tells them that this number should have lots of zeroes, which it does. When you start with a number such as 9000000000 and iterate to find a better and better description it doesn't take long to find the answer. 

However, trial and error doesn't tell you if you have missed any solutions, so there are better ways of solving the puzzle. A nice feature about this puzzle is that the digits of any integer that obeys my rules must sum to 10. That is because the number is effectively a tally. The number is tallying up how many of each digit there is in the number. As you are tallying 10 digits the sum of the digits will be 10.  With this knowledge I thought how can I partition 10 into different digits. You can split 10 up 42 ways among 10 digits. You can then try each partition of ten to see if it obeys the rules. This method of proving something is called proof by exhaustion. One problem with this proof, and often other cases of proof by exhaustion, is that it can take a long time to prove. Is there are quicker and simpler proof?

Yes there is! This proof also solves the puzzle for all possible size of number.

We have an n digit number: a₀,a₁,a₂,a₃……,a_n-1 

The first thing to note is that a₀>0. Otherwise, there would be a paradox as you no longer have an n digit number. 

Now let all the other non zero digits in the number other than a₀ be p. 

Now lets tally up all the non zero digits in the number. 

There are two ways of doing this. The first is to add up all the 1s then 2s then 3s... (n-1)s in the number. As the number is self descriptive that is equal to a₁+a₂+a₃....a_n-1

The other way of doing this is that we have already said that all the non zero digits other than a₀ in the number is equal to p and a₀ is non zero.
 Therefore, the tally of non zeroes is also equal to p+1.

This means that we have p non zero values adding to p+1, which tells us that most of the digits are going to be zeroes with the occasional 1 and 2, except for a_0.  

Now if a0>2, write j for a0.  Then put in 1 for aj which forces a₁=2 and a₂=1. Now when you put in j 0s to make a j+4 digit number which has a sum of values which is also j+4. Now we are done. No other values can be added without breaking it.

Therefore,  a>2 ⇒ We get solutions of the form j210...01000.  

To get the answers just sub in a value for n. These are the answers you get.

3211000

42101000

521001000 

6210001000

Interestingly if a≤2 then the length of the number will be short. This is because the sum of aj=n and all values are less than 2; meaning a_3, a4,a5 e.t.c are all equal to zero. This gives some special cases:

1210

2020

21200

I think that is everything I have to share about this puzzle. This puzzle can be taken even further if you change the base you are in. If you want a further challenge, try finding all the self-descriptive numbers in base 12. The next post will be online soon!