Monday, September 22, 2014

Quantitative Brain Teaser: Brain Only

I've recently been working some atrophied mental muscles and came across a brain teaser that was pretty nifty:
Find a 10-digit number, where each digit represents the number of that ordinal number in the whole number. So, the first digit represents the number of 0's in the whole 10 digits. The second digit represents the number of 1's in the whole 10 digits. And so on. The first digit is not a 0.

Example

If we shortened from 10 digits to 4 digit, the number
2,020
works since we have d0=2 and two 0's (in the second and fourth slots), d1=0 since the number has no 1's, d2=2 since the number has two 2's (in the first and third slots) and d3=0 since the number has no 3's.

Shorthand Notation

In order to refer to each digit, for search we name them all:
n=d0,d1d2d3,d4d5d6,d7d8d9.
We can see this in the above example when we refer to the digits in the four digit number
n=d0,d1d2d3.

A Practical Approach, Breaking Into Subproblems

Our search space is massive, and with only our wits, we need to quickly find a way to focus on a small space of possibilities. Since the first digit allows us to place a number of 0's we try to set it equal to values starting from the largest. By doing this we only have a little wiggle room to find the places which don't hold a zero.

First Case: d0=9

In this case our only choice is
9,000,000,000
since we must have nine 0's. However since we have one 9, d9=0 should not occur.

Thus we see none of our choices are possible when d0=9.

Second Case: d0=8

Here we must have eight 0's and d8>0 so our possible solutions must look like
8,000,000,00
But this leaves us with d8=1 as our only choice since we can't place any more 8's. But now the presence of a 1 in
8,000,000,010
can't coexist with d1=0 so we again see none of our choices are possible when d0=8.

Third Case: d0=7

Here we have seven 0's and know that d7=1. It must be at least 1 since the first digit is a 7. It can't be 2 because the presence of another 7 would mean another digit (other than 0) would occur 7 times, which is impossible since there are only 10 total digits.

Since we know d7=1 our possible solutions must look like
7,00,000,100
But again here we reach an impossible point. If we set d1=1 then that digit would contradict itself since it is the second occurrence of 1. If d1=2 it would contradict d2=0 and so on for higher values. In addition, we have used all our digits, so can't increase the value of d1 by placing more 1's in our number.

Thus we see none of our choices are possible when d0=7.

Fourth Case: d0=6

Here we have six 0's and must have d6=1 since (as above), two different digits can't occur six times among 10 digits.

Also as before we can't have d1=1 but now have some extra freedom (an extra digit which doesn't have to be 0) so consider the case d1=2. This corresponds to an occurrence of the digit 2, hence we set d2=1.

Now we have 4 non-zero digits along with six 0's to place:
6,210,001,000
Thus we have found a number which satisfies the criteria! The zero digits in the 3, 4, 5, 7, 8, and 9 places correspond to the absence of those digits. The non-zero digits in the 0, 1, 2, and 6 places also are the correct counts of each of those digits.

As a math nerd, I was still curious to know how to find every possible number that satisfies the criteria, but that task is too tedious to handle with the brain alone (or at least to be worth reading about when solved by hand). In my follow up to this, I'll show how a combination of smarts and programming can perform an exhaustive search in under 10 seconds.

No comments: