# Understanding a solution of USAMO 1999 (Integers having numerous partitions of a certain type)

For what values of $$n≥1$$ do there exist a number $$m$$ that can be written in the form $$a_1 + \cdots+ a_n$$ with $$a_1 \in \{1\}, a_2 \in \{1,2\},\cdots , a_n \in \{1,\ldots,n \}$$ in $$(n-1)!$$ or more ways?

Here's the solution:

I have made a box in red around the part that I didn't understand:

1. Why there must be only $$n-1$$ ordered tuples , and not $$n$$?

2. In the first inequality, they have assumed $$a_n =n$$, can anyone tell why?

3. Similarly, in the second inequality, we have $$a_n = 1$$, again I didn't get why. Also I am confused about the sign of inequality.

Any help will be much appreciated.

Thanks.

• Please don't use math mode for text. It looks bad. Oct 1, 2021 at 7:50
• @Arthur ok will take care of it from next time Oct 1, 2021 at 7:51
• I just added "integer-partitions" to your tag list. Besides, I have changed your title in order it is more in connection with its content (the fact that a certain Jim Propp has proposed a solution isn't important for example ...) Oct 1, 2021 at 8:30
• @JeanMarie thanks for improving the question Oct 1, 2021 at 9:32

I think it's illuminating to look more closely at the cases where such an $$n$$ exists, in order to understand the second part of the proof.

For instance, with $$n = 4$$ and $$m = 7$$, we are looking for ways to write $$7 = m = a_1 + a_2 + a_3 + a_4$$ where $$a_i \in \{1, \ldots, i\}$$. Moreover, there are at least $$(4-1)! = 6$$ ways to do this, and we can enumerate them as follows:

\begin{align} 7 &= 1 + 1 + 1 + 4 \\ &= 1 + 1 + 2 + 3 \\ &= 1 + 1 + 3 + 2 \\ &= 1 + 2 + 1 + 3 \\ &= 1 + 2 + 2 + 2 \\ &= 1 + 2 + 3 + 1. \\ \end{align}

We immediately notice that once we have selected the first three values, the fourth one is uniquely determined, since $$a_4 = m - (a_1 + a_2 + a_3)$$. And since there is only one way to choose $$a_1$$, two ways to choose $$a_2$$, and three ways to choose $$a_3$$, there are at most $$3!$$ such choices in total. And the same logic applies to the general case: for a given $$n$$, if such an $$m$$ satisfies the criteria, then there can be at most $$(n-1)!$$ choices for the ordered sequence $$(a_1, \ldots, a_{n-1})$$, because the last $$a_n$$ can never be free to be chosen in more than $$1$$ way, once the others are chosen.

For your second question, we see that since the criteria require there to be at least $$(n-1)!$$ ways to write $$m$$, and we have just established that there can be at most $$(n-1)!$$ ways to write $$m$$, that means there must be exactly $$(n-1)!$$ ways to write $$m$$, and each possible choice of $$a_i = \{1, \ldots, i\}$$ for $$i = 1, 2, \ldots, n-1$$, must result in a valid solution. And you can see this in the case $$n = 4$$, $$m = 7$$ above. Every one of the $$6$$ ways to pick $$(a_1, a_2, a_3)$$ from their respective sets is represented in the sum. So in particular, the "first" choice, where $$a_1 = a_2 = \ldots = a_{n-1} = 1$$, must be a valid choice, hence leads to the requirement $$m = 1 + 1 + \cdots + 1 + a_n = n-1 + a_n.$$ But the largest possible choice for $$a_n$$ is $$a_n = n$$, so this establishes the bound $$m \le n-1 + n = 2n-1.$$ Conversely, the "last" choice--i.e., the maximal choice for the $$a_1, \ldots, a_{n-1}$$, is $$a_i = i$$, hence $$m = 1 + 2 + \cdots + (n-1) + a_n = \frac{(n-1)n}{2} + a_n.$$ Since this too must be a valid solution, the smallest $$a_n$$ now furnishes a lower bound for $$m$$: $$m \ge \frac{(n-1)n}{2} + 1.$$ These two bounds, put together, lead to the final conclusion.

The idea behind the proof is this:

1. Show that if such an $$m$$ exists for a given $$n$$, then every possible choice of all the $$a_i$$s but the last $$a_n$$ must be permissible.
2. Show that the choice that requires the largest $$a_n$$ gives an upper bound on $$m$$.
3. Show that the choice that requires the smallest $$a_n$$ gives a lower bound on $$m$$.
4. Show that these upper and lower bounds combine to force $$n$$ to be within a certain range.
5. Furnish an example for each such $$n$$ in the range.
• great explanation, very well presented +10. I am just confused here (comment below). Oct 1, 2021 at 9:56
• So, is it that there is a unique $m$ for every $n$, or is it a matter of choice for $m$? I mean can't we choose $m=1+2+3+4=10$ for $n=4$? Oct 1, 2021 at 9:58
• @AbVk1718 Given $n$, you only need to find one $m$ that meets the criteria. For $n = 4$, we see that $m = 7$ works. But $m = 10$ does not, because while $10 = 1 + 2 + 3 + 4$, there are no other ways to make a sum of $10$ with only $n = 4$ terms. In order for a specific $n$ to satisfy the conditions of the problem, we need to find at least one $m$ for which there are $(n-1)!$ ways to make the same sum of $m$. You cannot change $m$; it has to be the same value for all $(n-1)!$ ways. Oct 1, 2021 at 10:25
• Thanks a lot @heropup, everything's cleared now Oct 1, 2021 at 10:37
1. Don't you agree that after fixing the first $$n-1$$ elements of this $$n$$-tuple $$(a_1,...a_n)$$, you get the last one trivially as $$a_n = m- \sum_{i=1}^{n-1}a_i$$ (that is, after fixing the first $$n-1$$ elements of the $$n$$-tuple, you fixed all elements)
2. Basically the idea here is to find the bounds for $$m$$ with respect to $$n$$ and since you need at least $$(n-1)!$$ tuples by the problem description and from 1. it follows that you have exactly $$(n-1)!$$ tuples in total, thus for every $$n-1$$ tuple $$(a_1,...a_{n-1})$$ there must exist $$a_n \in \{1,...,n\}$$ s.t. they all sum to $$m$$. In other words, if you take all ones, there has to be a number $$k$$ in $$\{1,...,n\}$$ s.t $$1+1+...+1 + k = m$$ ($$n-1$$ ones). It trivially follows that since this number is at most $$n$$ then $$m$$ is at most the sum of $$n-1$$ ones and $$n$$.
3. Exactly the same reasoning as for 2.
• Nice explanation, thanks @MDude Oct 1, 2021 at 10:37