Putnam 91/A6 solution

52nd Putnam 1991

Problem A6

An n-sum of type 1 is a finite sequence of positive integers a₁, a₂, ... , a_r, such that: (1) a₁ + a₂ + ... a_r = n; and (2) a₁ > a₂ + a₃, a₂ > a₃ + a₄, ... , a_r-2 > a_r-1 + a_r, and a_r-1 > a_r. 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 b₁, b₂, ... , b_s such that: (1) b₁ + b₂ + ... + b_s = n; (2) b₁ ≥ b₂ ≥ ... ≥ b_s; (3) each b_i is in the sequence 1, 2, 4, ... , g_j, ... defined by g₁ = 1, g₂ = 2, g_j = g_j-1 + g_j-2 + 1; and (4) if b₁ = g_k, then 1, 2, 4, ... , g_k 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 f_i be the usual Fibonacci sequence defined by f₁ = f₂ = 1, f_n = f_n-1 + f_n-2. A trivial induction gives that g_n = ∑₁ⁿ f_i.

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

Since a type 2 n-sum with b₁ = g_k is made up entirely of elements of {g₁, g₂, ... , g_k} and includes each element at least once, there is a bijection between such n-sums and sequences of non-negative numbers c₁, c₂, ... , c_k satisfying (c₁ + 1)g₁ + (c₂ + 1)g₂ + ... + (c_k + 1)g_k = n (*).

Suppose a_i is a type 1 n-sum with k terms. Then condition (2) implies that a_i ≥ a_i+1 + a_i+2 + 1, for i < k - 1, and a_k ≥ 1, a_k-1 ≥ 2. So a_i ≥ g_i. If we increase a_i above this minimum value, then that has a knock-on effect for a_j with j < i. In fact, we can write:
a_k = g₁ + c_kf₁;
a_k-1 = g₂ + c_kf₂ + c_k-1f₁;
a_k-2 = g₃ + c_kf₃ + c_k-1f₂ + c_k-2f₁;
...
a₁ = g_k + c_kf_k + c_k-1f_k-1 + ... + c₁f₁.

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

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

52nd Putnam 1991