64th Putnam 2003

Given n, how many ways can we write n as a sum of one or more positive integers a₁ ≤ a₂ ≤ ... ≤ a_k with a_k - a₁ = 0 or 1.

Answer

n

Solution

There is one way for each 1 ≤ k ≤ n. Induction on n. Obvious for n = 1. Write the solution with a > 0 Ns and b ≥ 0 (N+1)s as (a,b,N). Define a map f from the solutions for n to the solutions for n+1 by f(a,b,N) = (a-1,b+1,N) for a > 1 or (b+1,0,N+1) for a = 1. Define a map g from the solutions for n+1 excluding (n,0,1) to the solutions for n by g(a,b,N) = (a+1,b-1,N) for b ≥ 1 and (1,a-1,N-1) for b = 1. Evidently f and g are inverses, so each is a bijection. Hence there is one more solution for n+1 than for n.

64th Putnam 2003

© John Scholes
jscholes@kalva.demon.co.uk
8 Dec 2003
Last corrected/updated 8 Dec 03