2012 AIME I Problems/Problem 5

Problem 5

Let be the set of all binary integers that can be written using exactly zeros and ones where leading zeros are allowed. If all possible subtractions are performed in which one element of is subtracted from another, find the number of times the answer is obtained.

Solution

When a number in binary notation is subtracted by 1, it will contain the same number of digits as the original only if it originally ended in the digits "10". Therefore all the binary numbers that fit the conditions of this problem end in the digits "10". All the other 7 1's can be distributed in the remaining 11 spaces, and so the answer is .