2001 IMO Shortlist Problems/N6

Revision as of 02:19, 16 August 2011 by Mathmdmb (talk | contribs) (Solution)

Problem

Is it possible to find 100 positive integers not exceeding 25,000, such that all pairwise sums of them are different?

Solution

The answer is yes.


First Solution:

For example, let's say that the integers are, $k, k+a_1, k+a_2, ..., k+a_{99}$. Now this turns into a problem of solving for the $99$ integers $a_i$. This then each ai takes on the form, $j+b_1, j+b_2,..., j+b_{98}$. Then we must find the $98$ $b$ integers. By doing this process over and over again, we obtain the last $3$ numbers, $y, y+u_1, y+u_2$. Obviously these 3 integers can have different sums, and the number of different "parts" in every sequence (the number of terms that are different for $a_i, b_i, c_i$, etc.) is $99+98+\ldots+2$, not exceeding $25000$.

Second Solution:

Lemma: We try to show that for a prime $p$, there are such $p$ integers less than or equal to $2p^2$. Then it suffices because $p=101>100$ and $2\cdot 101^2<25000$ is enough.

Proof: $\qquad$Define $\bar a$ to be $a^2\equiv \bar a\bmod p$ and $\hat i=2pi+\bar i$. Then, we show that the integers $\hat i$ does the trick for $i=1$ to $p$. If $\hat a+\hat b\equiv \hat c+\hat d\pmod p$, then $2(a+b)p+\bar a+\bar b\equiv 2(c+d)p+\bar c+\bar d\pmod p$. Thus, we may say that \[a+b\equiv c+d\pmod p\qquad (\dag)\] and, \[\bar a+\bar b\equiv \bar c+\bar d\pmod p\qquad(*)\] since $\bar a<p$. From $(\dag)$, we have $a\equiv c+d-b\pmod p$. From $(*)$, we infer that \[a^2+b^2\equiv c^2+d^2\pmod p\] which gives us $(c+d-b)^2+b^2\equiv c^2+d^2\pmod p$. Factorizing, \[2(b^2-bc-bd+cd)\equiv0\pmod p\] \[\implies(b-c)(b-d)\equiv0\pmod p\]

This yields $p|b-c$ or $p|b-d$. But $|b-c|<p\implies b=c$, and this implies that $a=d$. The other case is similar. So, we are done. $\blacksquare$

Therefore, every sum must be distinct, as desired.

--03:19, 16 August 2011 (EDT)

See also