0
$\begingroup$

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:

USAMO 1999 submission, Jim Propp

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.

$\endgroup$
4
  • 1
    $\begingroup$ Please don't use math mode for text. It looks bad. $\endgroup$
    – Arthur
    Oct 1, 2021 at 7:50
  • 1
    $\begingroup$ @Arthur ok will take care of it from next time $\endgroup$
    – AbVk1718
    Oct 1, 2021 at 7:51
  • 1
    $\begingroup$ 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 ...) $\endgroup$
    – Jean Marie
    Oct 1, 2021 at 8:30
  • 1
    $\begingroup$ @JeanMarie thanks for improving the question $\endgroup$
    – AbVk1718
    Oct 1, 2021 at 9:32

2 Answers 2

2
$\begingroup$

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.
$\endgroup$
4
  • $\begingroup$ great explanation, very well presented +10. I am just confused here (comment below). $\endgroup$
    – AbVk1718
    Oct 1, 2021 at 9:56
  • $\begingroup$ 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$? $\endgroup$
    – AbVk1718
    Oct 1, 2021 at 9:58
  • 1
    $\begingroup$ @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. $\endgroup$
    – heropup
    Oct 1, 2021 at 10:25
  • $\begingroup$ Thanks a lot @heropup, everything's cleared now $\endgroup$
    – AbVk1718
    Oct 1, 2021 at 10:37
1
$\begingroup$
  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.
$\endgroup$
1
  • 1
    $\begingroup$ Nice explanation, thanks @MDude $\endgroup$
    – AbVk1718
    Oct 1, 2021 at 10:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.