Problem 12055
(American Mathematical Monthly, Vol.125, August-September 2018) Proposed by D. E. Knuth (USA).
Let (ai)i≥1 be a sequence of nonnegative integers with a1 ≥ a2 ≥ . . . and with finite sum. For a positive integer j, let bj be the number of indices i such that ai ≥ j. Prove that the multisets {a1+ 1, a2+ 2, . . . } and {b1+ 1, b2+ 2, . . . } are equal.
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
Solution. We show that the property holds by induction with respect to n ≥ 0, the number of non-zero terms of the sequence (ai)i≥1.
i) Base step. If n = 0 then
(ai)i≥1= (0, 0, 0, 0, . . . ) → {ai+ i}i≥1= {1, 2, 3, 4, . . . } (bj)j≥1= (0, 0, 0, 0, . . . ) → {bj+ j}j≥1= {1, 2, 3, 4, . . . } and the multisets are equal.
ii) Inductive step. If n ≥ 1 then (ai)i≥1 = (m, a2, . . . , an
| {z }
n
,0, . . . ) → {ai+ i}i≥1 = {m + 1, a2+ 2, . . . , an+ n
| {z }
n
, n+ 1, n + 2, . . . }
(bj)j≥1= (n, b2, . . . , bm
| {z }
m
,0, . . . ) → {bj+ j}j≥1= {n + 1, b2+ 2, . . . , bm+ m
| {z }
m
, m+ 1, m + 2, . . . }
where a1= m ≥ 1.
After removing m + 1 and subtracting one to each term, the multisets are equal if and only if {a2+ 1, . . . , an+ n − 1
| {z }
n−1
, n, n+ 1, . . . } = {n, b2+ 1, . . . , bm+ m − 1
| {z }
m
, m+ 1, . . . }.
Now the above equality holds by the inductive hypothesis applied to (ai+1)i≥1 = (a2, . . . , an
| {z }
n−1
,0, . . . ):
we have that (bj)j≥1= (n − 1, b2− 1, . . . , bm− 1
| {z }
m
,0, . . . ) and
{a2+ 1, . . . , an+ n − 1
| {z }
n−1
, n, n+1, . . . } = {ai+1+i}i≥1= {bj+j}j≥1= {n, b2+ 1, . . . , bm+ m − 1
| {z }
m
, m+1, . . . }.
