Problem:
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:
Let and be elements of with . Let denote the last two binary digits of and the last two binary digits of . There are four cases to consider:
The first and third cases are not possible, because then and would have different numbers of ones, so and could not both be in . In the fourth case, if an element of ends in , then adding to results in a number with fewer digits equal to one than , that is, the result of the addition cannot be in . However, if and , then and have the same number of digits equal to one, so if is in , then so is . Given these last two digits, the eleven preceding digits consist of seven ones and four zeros. These can be arranged in ways. Thus there are pairs in for which the difference is .
The problems on this page are the property of the MAA's American Mathematics Competitions