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"

(→‎Solution)
(→‎Solution)
Line 4: Line 4:
 
== Solution ==
 
== Solution ==
 
The answer is yes.
 
The answer is yes.
−
----
+
 
−
'''First Solution:'''
+
=== 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>.
 
  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.
+
=== 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>
+
''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>
 
<cmath>\implies(b-c)(b-d)\equiv0\pmod p</cmath>
  
Line 21: Line 22:
 
Therefore, every sum must be distinct, as desired.
 
Therefore, every sum must be distinct, as desired.
  
−
--03:19, 16 August 2011 (EDT)
+
 
 +
{{alternate solutions}}
  
 
== See also ==
 
== See also ==

Revision as of 02:43, 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.


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See also

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