Difference between revisions of "2010 IMO Problems/Problem 3"

m (Solution)
Line 64: Line 64:
  Thus, <math>g(x)=x+k</math>, <math>k\in\mathbb{N}</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


Find all functions $g:\mathbb{N}\rightarrow\mathbb{N}$ such that $\left(g(m)+n\right)\left(g(n)+m\right)$ is a perfect square for all $m,n\in\mathbb{N}.$

Author: Gabriel Carroll, USA


Suppose such function $g$ exist then:

Lemma 1) $g(m) \ne g(m+1)$

Assume for contradiction that  $g(m) = g(m+1)$
$\left(g(m+1)+m\right)\left(g(m)+m+1\right)$ has to be a perfect square

but $\left(g(m)+m\right)^2<\left(g(m+1)+m\right)\left(g(m)+m+1\right)<\left(g(m)+m+1\right)^2$.

A square cannot be between 2 consecutive squares. Contradiction. Thus,  $g(m) \ne g(m+1)$

Lemma 2) $|g(m)-g(m+1)| = 1$ (we have show that it can't be 0)

Assume for contradiction, that $|g(m)-g(m+1)| > 1$. 

Then there must exist a prime number $p$ such that $g(m)$ and $g(m+1)$ are in the same residue class modulo $p$.

If $|g(m)-g(m+1)| = p^aq$ where $q$ is not divisible by $p$.

If $a=1$.
Consider an $n$ such that $g(m)+n =p^3$
$g(m+1)+n = p^3 \pm pq =p (r)$ , where $r$ is not divisible by $p$

If $a>1$.
Consider an $n$ such that $g(m)+n =p$
$g(m+1)+n = p \pm p^aq =p (r)$ , where $r$ is not divisible by $p$

At least one of $g(n)+m$ , $g(n)+m+1$ is not divisible by $p$. Hence,
At least one of $(g(m+1)+n )(g(n)+m +1)$,  $(g(m)+n )(g(n)+m)$ is divisible by an odd amount of $p$. 

Hence, that number is not a perfect square.

If $g(m)-g(m+1) = 1$, then $g(x) = -x + k$, $k\in\mathbb{N}$.

$(g(1)+2)(g(2)+1)=(1+k)(-1+k)$, which is not perfect square because $(n)(n+2)$ is never a perfect square.

If $g(m)-g(m+1) = -1$, then $g(x) = x + k$, $k\in\mathbb{N}$.

Thus, $g(x)=x+k$, $k\in\mathbb{N}$

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
Invalid username
Login to AoPS