24th Putnam 1963

The sequence a₁, a₂, a₃, ... of positive integers is strictly monotonic increasing, a₂ = 2 and a_mn = a_ma_n for m, n relatively prime. Show that a_n = n.

Solution

The key observation is that if a_N = N for N odd, then a_2N = 2N, and hence a_N+1 = N+1, a_N+2 = N+2, ... , a_2N-1 = 2N-1 (because a_n is strictly increasing, so there are only N-1 holes for N-1 pegs. But we can now repeat using 2N-1 (provided 2N-1 > N, or N > 1) and the result is established for all n.

So we just need to get started with a₃. Suppose a₃ = m. Then a₆ = 2m. So m+2 ≤ a₅ ≤ 2m-1. Hence a₁₀ ≤ 4m-2 and a₉ ≤ 4m-3. So a₁₈ ≤ 8m-6 and hence a₁₅ ≤ 8m-9. But a₁₅ = a₃a₅ ≥ m²+2m, so m²+2m ≤ 8m-9 or (m-3)² ≤ 0. Hence m = 3.

24th Putnam 1963

© John Scholes
jscholes@kalva.demon.co.uk
5 Feb 2002