MathDB

A6

Part of 1991 Putnam

Problems(1)

sequences, n-sum of type 1/2

Source: Putnam 1991 A6

8/20/2021
An nn-sum of type 11 is a finite sequence of positive integers a1,a2,…,ara_1,a_2,\ldots,a_r, such that: (1)(1) a1+a2+…+ar=na_1+a_2+\ldots+a_r=n; (2)(2) a1>a2+a3,a2>a3+a4,…,ar−2>ar−1+ara_1>a_2+a_3,a_2>a_3+a_4,\ldots, a_{r-2}>a_{r-1}+a_r, and ar−1>ara_{r-1}>a_r. For example, there are five 77-sums of type 11, namely: 77; 6,16,1; 5,25,2; 4,34,3; 4,2,14,2,1. An nn-sum of type 22 is a finite sequence of positive integers b1,b2,…,bsb_1,b_2,\ldots,b_s such that: (1)(1) b1+b2+…+bs=nb_1+b_2+\ldots+b_s=n; (2)(2) b1≥b2≥…≥bsb_1\ge b_2\ge\ldots\ge b_s; (3)(3) each bib_i is in the sequence 1,2,4,…,gj,…1,2,4,\ldots,g_j,\ldots defined by g1=1g_1=1, g2=2g_2=2, gj=gj−1+gj−2+1g_j=g_{j-1}+g_{j-2}+1; and (4)(4) if b1=gkb_1=g_k, then 1,2,4,…,gk1,2,4,\ldots,g_k is a subsequence. For example, there are five 77-sums of type 22, namely: 4,2,14,2,1; 2,2,2,12,2,2,1; 2,2,1,1,12,2,1,1,1; 2,1,1,1,1,12,1,1,1,1,1; 1,1,1,1,1,1,11,1,1,1,1,1,1. Prove that for n≥1n\ge1 the number of type 11 and type 22 nn-sums is the same.