Difference between revisions of "2001 IMO Shortlist Problems/N6"
(→Solution) |
m (→First Solution) |
||
(One intermediate revision by one other user not shown) | |||
Line 4: | Line 4: | ||
== Solution == | == Solution == | ||
The answer is yes. | 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 === | |
− | |||
− | |||
− | 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> | + | '''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> | <cmath>\implies(b-c)(b-d)\equiv0\pmod p</cmath> | ||
Line 21: | Line 20: | ||
Therefore, every sum must be distinct, as desired. | Therefore, every sum must be distinct, as desired. | ||
− | + | ||
+ | {{alternate solutions}} | ||
== See also == | == See also == |
Latest revision as of 13:08, 17 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.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.