A 10 digit positive integer is called a
cute number if its digits are from the set {1,2,3} and every two consecutive digits differ by one.
a. Prove that exactly five digits of a cute number are equal to 2.
b. Find the total number of cute numbers.
c. Prove that the sum of all cute numbers is divisible by 1408.
Source: Romanian math competition
a. The digit after each 2 must be a non2, and after each non2 must be a 2, so 2's and non2's alternate.
b. The 1's and 3's, the count of which adds to 5, can be considered like a binary number of 5 bits. Taken by themselves there are 2^5 possibilities. But there's also the choice of whether to start the number with the first non2, or to start with the first 2, so altogether there are 2^6 cute numbers.
c. The sum of all cute numbers needs to be a multiple of 1111111111, as each digit position's value in the sum, without regard to "carries", is the same. That number, 1111111111, is divisible by 11, the only prime factor of 1408 other than 2 (1408 = 2^7 * 11). So now we need only show that the sum of any individual position's values is a multiple of 2^7.
Half of the 2^6 cute numbers have a 2 in any given position. The other half are evenly divided between 1 and 3; the total of the 1's and 3's is the same as if they were all 2's. So there are the equivalent of 2^6 2's being added together, for a total of 2^7, precisely what we said we needed. QED

Posted by Charlie
on 20180201 11:24:36 