Let N be the positive integers. Define f : N → {0, 1} by f(n) = 1 if the number of 1s in the binary representation of n is odd and 0 otherwise. Show that there do not exist positive integers k and m such that f(k + j) = f(k + m + j) = f(k + 2m + j) for 0 ≤ j < m.
Solution
Note that f(2n) ≠ f(2n+1). So f(n), f(n+1), f(n+2) cannot all be equal, which establishes the case m = 1.
Note that the condition f(k + j) = f(k + m + j) = f(k + 2m + j) for 0 ≤ j < m can alternatively be written as f(k + j) = f(k + j + m) for 0 ≤ j < 2m.
f(4n+1) = f(4n+2), so we cannot have f(a) = f(b) and f(a+1) = f(b+1) if a is even and b = 1 (mod 4). This is sufficient to establish the case m odd and > 1. For suppose k is even. Then either k+m or k+m+2 = 1 (mod 4). So taking a = k and b = whichever of k+m and k+m+2 is 1 mod 4, we cannot have f(a) = f(b) and f(a+1) = f(b+1). Similarly, if k is odd, then either k or k+2 is 1 mod 4 and both k+m and k+m+2 are even.
It remains to consider m even. But given a case with 2m we can always find another case with m. Repeating we would eventually reach a case with m odd. So even cases cannot exist either.
Since f(2n) = f(n) the case 2k, 2m immediately gives the case k, m. Just select the even j: f(2k + 2j) = f(2k + 2j + 2m) for 0 ≤ j < m and deduce f(k + j) = f(k + j + m) for 0 ≤ j < m, which is the case k, m. Similarly, the case 2k+1, 2m gives the case k+1, m.
© John Scholes
jscholes@kalva.demon.co.uk
7 Jan 2001