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

Question

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.

Answer 1

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.

Answer 2

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.