Given n, how many ways can we write n as a sum of one or more positive integers a1 ≤ a2 ≤ ... ≤ ak with ak - a1 = 0 or 1.
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
8 Dec 2003
Last corrected/updated 8 Dec 03