### 52nd Putnam 1991

Problem A6

An n-sum of type 1 is a finite sequence of positive integers a1, a2, ... , ar, such that: (1) a1 + a2 + ... ar = n; and (2)   a1 > a2 + a3,   a2 > a3 + a4, ... , ar-2 > ar-1 + ar, and ar-1 > ar. For example, there are five 7-sums of type 1, namely: 7; 6, 1; 5, 2; 4, 3; 4, 2, 1.

An n-sum of type 2 is a finite sequence of positive integers b1, b2, ... , bs such that: (1) b1 + b2 + ... + bs = n; (2) b1 ≥ b2 ≥ ... ≥ bs; (3) each bi is in the sequence 1, 2, 4, ... , gj, ... defined by g1 = 1, g2 = 2, gj = gj-1 + gj-2 + 1; and (4) if b1 = gk, then 1, 2, 4, ... , gk is a subsequence. For example, there are five 7-sums of type 2, namely: 4, 2, 1; 2, 2, 2, 1; 2, 2, 1, 1, 1; 2, 1, 1, 1, 1, 1; 1, 1, 1, 1, 1, 1, 1.

Prove that for n ≥ 1 the number of type 1 and type 2 n-sums is the same.

Solution

Moderately hard.

Let fi be the usual Fibonacci sequence defined by f1 = f2 = 1, fn = fn-1 + fn-2. A trivial induction gives that gn = ∑1n fi.

We show that there is a bijection between n-sums of type 2 with b1 = gk and n sums of type 1 with k members.

Since a type 2 n-sum with b1 = gk is made up entirely of elements of {g1, g2, ... , gk} and includes each element at least once, there is a bijection between such n-sums and sequences of non-negative numbers c1, c2, ... , ck satisfying (c1 + 1)g1 + (c2 + 1)g2 + ... + (ck + 1)gk = n (*).

Suppose ai is a type 1 n-sum with k terms. Then condition (2) implies that ai ≥ ai+1 + ai+2 + 1, for i < k - 1, and ak ≥ 1, ak-1 ≥ 2. So ai ≥ gi. If we increase ai above this minimum value, then that has a knock-on effect for aj with j < i. In fact, we can write:
ak = g1 + ckf1;
ak-1 = g2 + ckf2 + ck-1f1;
ak-2 = g3 + ckf3 + ck-1f2 + ck-2f1;
...
a1 = gk + ckfk + ck-1fk-1 + ... + c1f1.

Since the sum of the ai is n, the ci satisfy (*). Conversely, if ci are any non-negative numbers satisfying (*), then the relations above give a type 1 n-sum ai. So we have a bijection between type 1 n-sums with k members and non-negative ci satisfying (*). Putting the two bijections together gives the claimed bijection between type 2 n-sums with largest member gk and type 1 n-sums with k members.

It follows that there is a bijection between type 1 and type 2 n-sums.