Monday, March 14, 2011

10 Digit Number Problem

en-digit number. Find a 10-digit number whose first digit
is the number of 1’s in the 10-digit number, whose second
digit is the number of 2’s in the 10-digit number, whose
third digit is the number of 3’s in the 10-digit number, and
so on. The ninth digit must be the number of nines in the
10-digit number and the tenth digit must be the number of
zeros in the 10-digit number

I'll denote the digits a%5B1%5D, a%5B2%5D, ..., a%5B10%5D. Since there are a%5B1%5D 1's, a%5B2%5D 2's, ..., a%5B10%5D 0's, then sum%28a%5Bi%5D%2C+i+=+1%2C+10%29+=+10 because there are ten digits in the number.

Suppose a%5B10%5D+=+0. Then a contradiction would result, since there is at least one zero, so a%5B10%5D+%3E=+1.

Suppose a%5B10%5D+=+1. Then, this implies that there is exactly one zero within the number, and all the other a%5Bi%5D's are at least one, which also creates a contradiction due to the sum of digits. This can also apply to higher values of a%5B10%5D. If a%5B10%5D+=+n, then sum%28a%5Bi%5D%2C+i+=+1%2C+9%29+=+10-n. Also, if n of the numbers { a%5B1%5D, a%5B2%5D, ..., a%5B9%5D } are zero, then 9-n of these numbers are greater than or equal to 1, and they sum up to 10-n.

By the Pigeonhole principle, exactly one of the 9-n numbers is equal to 2 and all other nonzero numbers are equal to 1 (this means, 8-n numbers equal to 1). Therefore the number has n zeros, 8-n 1's and one 2. We can easily guess and check based on the value of n, which can only range between 2 and 8. We see that the number 2100010006 satisfies all the given constraints, which happens when n+=+6.

No comments: