Putnam 2003 A1 – Quirky Quintet

Let $n$ be a fixed positive integer. How many ways are there to write $n$ as a sum of positive integers, $n = a_1 + a_2 + \cdots + a_k,$ with $k$ an arbitrary positive integer and $a_1 \le a_2 \le \cdots \le a_k \le a_1 + 1$ ? For example with $n = 4$ , there are 4 ways: $4, 2 + 2, 1 + 1+ 2, 1+1+1+1.$

Solution: Denote $K_n$ to be the set of tuples of $(a_1, \ldots, a_k)$ with the above properties. We claim that $|K_n| = n$ . We will use induction. It is easy to verify the claim for $|K_n| = 1,2,3,4$ for $n = 1,2,3,4$ respectively.

Assume that $|K_{l}| = l$ for some positive integer $l$ , then for a given tuple $(a_1, \ldots, a_k) \in K_l$ we can add 1 to one of the elements in the tuple, and still preserve the property that $a_1 \le a_2 \le \cdots \le a_k \le a_1 + 1$ . If $a_1 \not = a_k$ , then we simply can add 1 where the integers jump, otherwise $a_1 = a_2 = \cdots = a_k$ and we can just have $a_k + 1$ . This gives rise to tuples which are in $K_{l+1}$ . Finally, we have a tuple of 1s to add; this results in $|K_{l+1}| = l+1$ .

We are not done here, as we would need to show that there exists no other tuples in $K_{l+1}$ that we cannot construct as above. This is easy to see, as we can do the inverse operation of subtracting one (with the exception of the tuple of all 1s).

Leave a Reply Cancel reply