### 10th Putnam 1950

Problem A6

Let f(x) = ∑0 anxn and suppose that each an = 0 or 1. Do either (1) or (2):

(1)   Show that if f(1/2) is rational, then f(x) has the form p(x)/q(x) for some integer polynomials p(x) and q(x).

(2)   Show that if f(1/2) is not rational, then f(x) does not have the form p(x)/q(x) for any integer polynomials p(x) and q(x).

Solution

(1) f(1/2) is the binary expansion of some real in the closed interval [0, 1]. So if it is rational, then the binary expansion is periodic after some point. In other words, there are positive integers N and k such that an = an+k for n > N. Hence f(x) = a0 + a1x + ... + aNxN + (aN+1xN+1 + ... + aN+k-1xN+k-1)(1 + xk + x2k + ... ) = a0 + a1x + ... + aNxN + (aN+1xN+1 + ... + aN+k-1xN+k-1)/(1 - xk). Hence we can take q(x) = 1 - xk and p(x) = (a0 + a1x + ... + aNxN)(1 - xk) + (aN+1xN+1 + ... + aN+k-1xN+k-1).

(2) is trivial. If f(x) = p(x)/q(x), then f(1/2) = p(1/2)/q(1/2) which is rational. The only slight complication is if q(1/2) = 0. But we can assume that p(x)/q(x) is in lowest terms, so if q(1/2) = 0, then p(x) is non-zero, but then p(x) = f(x) q(x). We know that f(1/2) ≤ 1/2 + 1/4 + 1/8 + ... = 1, so f(1/2) q(1/2) = 0. Hence p(1/2) = 0. Contradiction.