Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2001 IMO Shortlist Problems/N6"

m (fix latex)
(→‎Solution)
Line 3: Line 3:
  
 
== Solution ==
 
== Solution ==
−
For example, let's say that the integers are, <math>k, k+a_1, k+a_2, ..., k+a_{99}</math>. Now this turns into a problem of solving for the <math>99</math> integers <math>a_i</math>. This then each ai takes on the form, <math>j+b_1, j+b_2,..., j+b_{98}</math>. Then we must find the <math>98</math> <math>b</math> integers. By doing this process over and over again, we obtain the last <math>3</math> numbers, <math>y, y+u_1, y+u_2</math>. 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 <math>a_i, b_i, c_i</math>, etc.) is <math>99+98+\ldots+2</math>, not exceeding <math>25000</math>.
+
The answer is yes.
 +
----
 +
'''First Solution:'''
 +
 
 +
For example, let's say that the integers are, <math>k, k+a_1, k+a_2, ..., k+a_{99}</math>. Now this turns into a problem of solving for the <math>99</math> integers <math>a_i</math>. This then each ai takes on the form, <math>j+b_1, j+b_2,..., j+b_{98}</math>. Then we must find the <math>98</math> <math>b</math> integers. By doing this process over and over again, we obtain the last <math>3</math> numbers, <math>y, y+u_1, y+u_2</math>. 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 <math>a_i, b_i, c_i</math>, etc.) is <math>99+98+\ldots+2</math>, not exceeding <math>25000</math>.
 +
 
 +
----
 +
'''Second Solution:'''
 +
 
 +
''Lemma:'' We try to show that for a prime <math>p</math>, there are such <math>p</math> integers less than or equal to <math>2p^2</math>. Then it suffices because <math>p=101>100</math> and <math>2\cdot 101^2<25000</math> is enough.
 +
 
 +
Proof: <math>\qquad</math>Define <math>\bar a</math> to be <math>a^2\equiv \bar a\bmod p</math> and <math>\hat i=2pi+\bar i</math>. Then, we show that the integers <math>\hat i</math> does the trick for <math>i=1</math> to <math>p</math>. If <math>\hat a+\hat b\equiv \hat c+\hat d\pmod p</math>, then <math>2(a+b)p+\bar a+\bar b\equiv 2(c+d)p+\bar c+\bar d\pmod p</math>. Thus, we may say that <cmath>a+b\equiv c+d\pmod p\qquad (\dag)</cmath> and, <cmath>\bar a+\bar b\equiv \bar c+\bar d\pmod p\qquad(*)</cmath> since <math>\bar a<p</math>. From <math>(\dag)</math>, we have <math>a\equiv c+d-b\pmod p</math>. From <math>(*)</math>, we infer that <cmath>a^2+b^2\equiv c^2+d^2\pmod p</cmath> which gives us <math>(c+d-b)^2+b^2\equiv c^2+d^2\pmod p</math>. Factorizing, <cmath>2(b^2-bc-bd+cd)\equiv0\pmod p</cmath>
 +
<cmath>\implies(b-c)(b-d)\equiv0\pmod p</cmath>
 +
 
 +
This yields <math>p|b-c</math> or <math>p|b-d</math>. But <math>|b-c|<p\implies b=c</math>, and this implies that <math>a=d</math>. The other case is similar. So, we are done.  <math>\blacksquare</math>
 +
 
 +
Therefore, every sum must be distinct, as desired.
 +
 
 +
--03:19, 16 August 2011 (EDT)
  
 
== See also ==
 
== See also ==

Revision as of 02:19, 16 August 2011

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2001_IMO_Shortlist_Problems/N6&oldid=41521"