IMO 1994 SL N5

Origin: ROM | Category: Number Theory

Problem

For any positive integer k, Ak is the subset of {k+1, k+ 2, . . . , 2k} consisting of all elements whose digits in base 2 contain exactly three 1’s. Let f(k) denote the number of elements in Ak. (a) Prove that for any positive integer m, f(k) = m has at least one

Solution

(a) Denote by b(n) the number of 1’s in the binary representation of n. Since b(2k + 2) = b(k + 1) and b(2k + 1) = b(k) + 1, we deduce that f(k + 1) = . f(k) + 1, if b(k) = 2; f(k), otherwise. (1) The set of k’s with b(k) = 2 is infinite, so it follows that f(k) is unbounded. Hence f takes all natural values.

(b) Since f is increasing, k is a unique solution of f(k) = m if and only if f(k −1) < f(k) < f(k + 1). By (1), this inequality is equivalent to b(k −1) = b(k) = 2. It is easy to see that then k −1 must be of the form 2t + 1 for some t. In this case, {k + 1, . . . , 2k} contains the number 2t+1 + 3 = 10 . . .0112 and t(t−1) binary (t + 1)-digit numbers with three 1’s, so m = f(k) = t(t−1)