Difference between revisions of "2010 IMO Problems/Problem 3"
m (→Solution) |
m |
||
(3 intermediate revisions by the same user not shown) | |||
Line 11: | Line 11: | ||
Lemma 1) <math>g(m) \ne g(m+1)</math> | Lemma 1) <math>g(m) \ne g(m+1)</math> | ||
− | Assume for contradiction that <math>g(m) = g(m+1)</math> | + | Assume for contradiction that <math>g(m) = g(m+1)</math> |
<math>\left(g(m+1)+m\right)\left(g(m)+m+1\right)</math> has to be a perfect square | <math>\left(g(m+1)+m\right)\left(g(m)+m+1\right)</math> has to be a perfect square | ||
Line 23: | Line 23: | ||
Lemma 2) <math>|g(m)-g(m+1)| = 1</math> (we have show that it can't be 0) | Lemma 2) <math>|g(m)-g(m+1)| = 1</math> (we have show that it can't be 0) | ||
− | Assume for contradiction, that <math>|g(m)-g(m+1)| > 1</math>. Then there must exist a prime number <math>p</math> such that <math>g(m)</math> and <math>g(m+1)</math> are in the same residue class modulo <math>p</math>. | + | Assume for contradiction, that <math>|g(m)-g(m+1)| > 1</math>. |
+ | |||
+ | Then there must exist a prime number <math>p</math> such that <math>g(m)</math> and <math>g(m+1)</math> are in the same residue class modulo <math>p</math>. | ||
If <math>|g(m)-g(m+1)| = p^aq</math> where <math>q</math> is not divisible by <math>p</math>. | If <math>|g(m)-g(m+1)| = p^aq</math> where <math>q</math> is not divisible by <math>p</math>. | ||
<br /> | <br /> | ||
− | If <math>a=1</math>. | + | If <math>a=1</math>. |
− | Consider an <math>n</math> such that <math>g(m)+n =p^3</math> | + | Consider an <math>n</math> such that <math>g(m)+n =p^3</math> |
− | <math>g(m+1)+n = p^3 \pm pq =p (r)</math> , where <math>r</math> is not divisible by <math>p</math> | + | <math>g(m+1)+n = p^3 \pm pq =p (r)</math> , where <math>r</math> is not divisible by <math>p</math> |
<br /> | <br /> | ||
− | If <math>a>1</math>. | + | If <math>a>1</math>. |
− | Consider an <math>n</math> such that <math>g(m)+n =p</math> | + | Consider an <math>n</math> such that <math>g(m)+n =p</math> |
− | <math>g(m+1)+n = p \pm p^aq =p (r)</math> , where <math>r</math> is not divisible by <math>p</math> | + | <math>g(m+1)+n = p \pm p^aq =p (r)</math> , where <math>r</math> is not divisible by <math>p</math> |
<br /><br /> | <br /><br /> | ||
− | At least one of <math>g(n)+m</math> , <math>g(n)+m+1</math> is not divisible by <math>p</math>. Hence, | + | At least one of <math>g(n)+m</math> , <math>g(n)+m+1</math> is not divisible by <math>p</math>. Hence, |
− | At least one of <math>(g(m+1)+n )(g(n)+m +1)</math>, <math>(g(m)+n )(g(n)+m)</math> is divisible by an odd amount of <math>p</math>. | + | At least one of <math>(g(m+1)+n )(g(n)+m +1)</math>, <math>(g(m)+n )(g(n)+m)</math> is divisible by an odd amount of <math>p</math>. |
Hence, that number is not a perfect square. | Hence, that number is not a perfect square. | ||
<br /><br /> | <br /><br /> | ||
− | Thus, <math>g(x)=x+k</math>, <math>k\in\mathbb{N}</math> | + | |
+ | If <math>g(m)-g(m+1) = 1</math>, then <math>g(x) = -x + k</math>, <math>k\in\mathbb{N}</math>. | ||
+ | |||
+ | <math>(g(1)+2)(g(2)+1)=(1+k)(-1+k)</math>, which is not perfect square because <math>(n)(n+2)</math> is never a perfect square. | ||
+ | |||
+ | If <math>g(m)-g(m+1) = -1</math>, then <math>g(x) = x + k</math>, <math>k\in\mathbb{N}</math>. | ||
+ | |||
+ | <math>(g(m)+n)(g(n)+m)=(n+m+k)^2</math> | ||
+ | |||
+ | Thus, <math>g(x)=x+k</math>, <math>k\in\mathbb{N}</math> | ||
+ | |||
+ | == See Also == | ||
+ | {{IMO box|year=2010|num-b=2|num-a=4}} |
Latest revision as of 23:53, 23 October 2010
Problem
Find all functions such that
is a perfect square for all
Author: Gabriel Carroll, USA
Solution
Suppose such function exist then:
Lemma 1)
Assume for contradiction that![]()
has to be a perfect square
but .
A square cannot be between 2 consecutive squares. Contradiction. Thus,![]()
Lemma 2) (we have show that it can't be 0)
Assume for contradiction, that.
Then there must exist a prime number such that
and
are in the same residue class modulo
.
If where
is not divisible by
.
If.
Consider ansuch that
![]()
, where
is not divisible by
![]()
If.
Consider ansuch that
![]()
, where
is not divisible by
![]()
At least one of,
is not divisible by
. Hence,
At least one of,
is divisible by an odd amount of
.
Hence, that number is not a perfect square.
If , then
,
.
, which is not perfect square because
is never a perfect square.
If , then
,
.
Thus,,
![]()
See Also
2010 IMO (Problems) • Resources | ||
Preceded by Problem 2 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 4 |
All IMO Problems and Solutions |