### 64th Putnam 2003

**Problem A1**
Given n, how many ways can we write n as a sum of one or more positive integers a_{1} ≤ a_{2} ≤ ... ≤ a_{k} with a_{k} - a_{1} = 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