Putnam 50/A6 solution

10th Putnam 1950

Problem A6

Let f(x) = ∑₀^∞ a_nxⁿ and suppose that each a_n = 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 a_n = a_n+k for n > N. Hence f(x) = a₀ + a₁x + ... + a_Nx^N + (a_N+1x^N+1 + ... + a_N+k-1x^N+k-1)(1 + x^k + x^2k + ... ) = a₀ + a₁x + ... + a_Nx^N + (a_N+1x^N+1 + ... + a_N+k-1x^N+k-1)/(1 - x^k). Hence we can take q(x) = 1 - x^k and p(x) = (a₀ + a₁x + ... + a_Nx^N)(1 - x^k) + (a_N+1x^N+1 + ... + a_N+k-1x^N+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.

10th Putnam 1950