Difference between revisions of "1986 IMO Problems/Problem 1"
Durianaops (talk | contribs) |
Lovematch13 (talk | contribs) m (→Solution 1: Got rid of informal slang (changed mods to modular arithmetic)) |
||
(6 intermediate revisions by 3 users not shown) | |||
Line 6: | Line 6: | ||
===Solution 1=== | ===Solution 1=== | ||
− | We do casework with | + | We do casework with modular arithmetic. |
<math>d\equiv 0,3 \pmod{4}: 13d-1</math> is not a perfect square. | <math>d\equiv 0,3 \pmod{4}: 13d-1</math> is not a perfect square. | ||
Line 25: | Line 25: | ||
Suppose <math>p^2=2d-1</math>, <math>q^2=5d-1</math> and <math>r^2=13d-1</math>. From the first equation, <math>p</math> is an odd integer. Let <math>p=2k-1</math>. We have <math>d=2k^2-2k+1</math>, which is an odd integer. Then <math>q^2</math> and <math>r^2</math> must be even integers, denoted by <math>4n^2</math> and <math>4m^2</math> respectively, and thus <math>r^2-q^2=4m^2-4n^2=8d</math>, from which | Suppose <math>p^2=2d-1</math>, <math>q^2=5d-1</math> and <math>r^2=13d-1</math>. From the first equation, <math>p</math> is an odd integer. Let <math>p=2k-1</math>. We have <math>d=2k^2-2k+1</math>, which is an odd integer. Then <math>q^2</math> and <math>r^2</math> must be even integers, denoted by <math>4n^2</math> and <math>4m^2</math> respectively, and thus <math>r^2-q^2=4m^2-4n^2=8d</math>, from which | ||
<cmath>2d=m^2-n^2=(m+n)(m-n)</cmath> can be deduced. Since <math>m^2-n^2</math> is even, <math>m</math> and <math>n</math> have the same parity, so <math>(m+n)(m-n)</math> is divisible by <math>4</math>. It follows that the odd integer <math>d</math> must be divisible by <math>2</math>, leading to a contradiction. We are done. | <cmath>2d=m^2-n^2=(m+n)(m-n)</cmath> can be deduced. Since <math>m^2-n^2</math> is even, <math>m</math> and <math>n</math> have the same parity, so <math>(m+n)(m-n)</math> is divisible by <math>4</math>. It follows that the odd integer <math>d</math> must be divisible by <math>2</math>, leading to a contradiction. We are done. | ||
+ | |||
{{alternate solutions}} | {{alternate solutions}} | ||
{{IMO box|year=1986|before=First Problem|num-a=2}} | {{IMO box|year=1986|before=First Problem|num-a=2}} |
Latest revision as of 15:02, 31 July 2022
Contents
Problem
Let be any positive integer not equal to
or
. Show that one can find distinct
in the set
such that
is not a perfect square.
Solution
Solution 1
We do casework with modular arithmetic.
is not a perfect square.
is not a perfect square.
Therefore, Now consider
is not a perfect square.
is not a perfect square.
As we have covered all possible cases, we are done.
Solution 2
Proof by contradiction:
Suppose ,
and
. From the first equation,
is an odd integer. Let
. We have
, which is an odd integer. Then
and
must be even integers, denoted by
and
respectively, and thus
, from which
can be deduced. Since
is even,
and
have the same parity, so
is divisible by
. It follows that the odd integer
must be divisible by
, leading to a contradiction. We are done.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
1986 IMO (Problems) • Resources | ||
Preceded by First Problem |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 2 |
All IMO Problems and Solutions |