IMO 1979 SL 8

Origin: FRG

Problem

For all rational x satisfying 0 \leqx < 1, f is defined by f(x) = f(2x)/4, for 0 \leqx < 1/2, 3/4 + f(2x −1)/4, for 1/2 \leqx < 1. Given that x = 0.b1b2b3 . . . is the binary representation of x, find f(x).

Solution

By the definition of f, it holds that f(0.b1b2 . . . ) = 3b1/4+f(0.b2b3 . . . )/4 = 0.b1b1 + f(0.b2b3 . . . )/4. Continuing this argument we obtain f(0.b1b2b3 . . . ) = 0.b1b1 . . . bnbn + 22n f(0.bn+1bn+2 . . . ). (1) The binary representation of every rational number is eventually periodic. Let us first determine f(x) for a rational x with the periodic representation x = 0.b1b2 . . . bn. Using (1) we obtain f(x) = 0.b1b1 . . . bnbn + f(x)/22n, and hence f(x) = 2n 2n−10.b1b1 . . . bnbn = 0.b1b1 . . . bnbn. Now let x = 0.a1a2 . . . akb1b2 . . . bn be an arbitrary rational number. Then it follows from (1) that f(x) = 0.a1a1 . . . akak + 1 22n f(0.b1b2 . . . bn) = 0.a1a1 . . . akakb1b1 . . . bnbn. Hence f(0.b1b2 . . . ) = 0.b1b1b2b2 . . . for every rational number 0.b1b2 . . . .