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 03: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,. Now this turns into a problem of solving for the
integers
. This then each ai takes on the form,
. Then we must find the
![]()
integers. By doing this process over and over again, we obtain the last
numbers,
. 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
, etc.) is
, not exceeding
.
Second Solution:
Lemma: We try to show that for a prime , there are such
integers less than or equal to
. Then it suffices because
and
is enough.
Proof: Define
to be
and
. Then, we show that the integers
does the trick for
to
. If
, then
. Thus, we may say that
and,
since
. From
, we have
. From
, we infer that
which gives us
. Factorizing,
This yields or
. But
, and this implies that
. The other case is similar. So, we are done.
Therefore, every sum must be distinct, as desired.
--03:19, 16 August 2011 (EDT)