2003 Putnam

Probability Level 3

How many ways are there to write $10^5$ as a sum of positive integers, $10^5=a_1+a_2+\cdots +a_k$ with k being an arbitrary positive integer and $a_1\leq a_2 \leq \cdots \leq a_1+1$ ? For example, with $n=4$ , there are four ways: $4,2+2,2+1+1,1+1+1+1$ .

The answer is 100000.

1 solution

Patrick Corn
Jan 15, 2021

Let $n = 10^5.$ Every such representation consists of some copies (at least one) of $a$ and some copies (at least zero) of $a+1,$ i.e. $n = (a+a+\cdots+a)+((a+1)+(a+1)+\cdots+(a+1).$ If there are $r$ copies of $a+1,$ this turns into $n = ka+r, \ \ 0 \le r < k.$ Well, given any positive integer $k \le n,$ there is exactly one $a$ and $r$ that satisfy this equation, by the division algorithm . So the number of solutions is equal to the number of positive integers $k \le n,$ which is just $n.$ In this case the answer is $n = \fbox{100000}.$

(FYI: I edited the problem to specify a sum of positive integers, as otherwise we could have a sum of arbitrarily many zeroes and $n$ ones.)

2003 Putnam

The answer is 100000.

1 solution

0 pending reports