IMO 1994/A3 solution

IMO 1994

Problem A3

For any positive integer k, let f(k) be the number of elements in the set {k+1, k+2, ... , 2k} which have exactly three 1s when written in base 2. Prove that for each positive integer m, there is at least one k with f(k) = m, and determine all m for which there is exactly one k.

Answer

2, 4, ... , n(n-1)/2 + 1, ... .

Solution

To get a feel, we calculate the first few values of f explicitly:

f(2) = 0, f(3) = 0
f(4) = f(5) = 1, [7 = 111]
f(6) = 2, [7 = 111, 11 = 1011]
f(7) = f(8) = f(9) = 3 [11 = 1011, 13 = 1101, 14 = 1110]
f(10) = 4 [11, 13, 14, 19 = 10011]
f(11) = f(12) = 5 [13, 14, 19, 21 = 10101, 22 = 10110]
f(13) = 6 [14, 19, 21, 22, 25 = 11001, 26 = 11010]

We show that f(k+1) = f(k) or f(k) + 1. The set for k+1 has the additional elements 2k+1 and 2k+2 and it loses the element k+1. But the binary expression for 2k+2 is the same as that for k+1 with the addition of a zero at the end, so 2k+2 and k+1 have the same number of 1s. So if 2k+1 has three 1s, then f(k+1) = f(k) + 1, otherwise f(k+1) = f(k). Now clearly an infinite number of numbers 2k+1 have three 1s, (all numbers 2^r + 2^s + 1 for r > s > 0). So f(k) increases without limit, and since it only moves up in increments of 1, it never skips a number. In other words, given any positive integer m we can find k so that f(k) = m.

From the analysis in the last paragraph we can only have a single k with f(k) = m if both 2k-1 and 2k+1 have three 1s, or in other words if both k-1 and k have two 1s. Evidently this happens when k-1 has the form 2ⁿ + 1. This determines the k, namely 2ⁿ + 2, but we need to determine the corresponding m = f(k). It is the number of elements of {2ⁿ+3, 2ⁿ+4, ... , 2ⁿ⁺¹+4} which have three 1s. Elements with three 1s are either 2ⁿ+2^r+2^s with 0 ≤ r < s < n, or 2ⁿ⁺¹+3. So there are m= n(n-1)/2 + 1 of them. As a check, for n = 2, we have k = 2²+2 = 6, m = 2, and for n = 3, we have k = 2³+2 = 10, m = 4, which agrees with the f(6) = 2, f(10) = 4 found earlier.

35th IMO 1994