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

(Created page with '== Problem == Find all functions <math>g:\mathbb{N}\rightarrow\mathbb{N}</math> such that <math>\left(g(m)+n\right)\left(g(n)+m\right)</math> is a perfect square for all <math>m…') |
m |
||

Line 4: | Line 4: | ||

''Author: Gabriel Carroll, USA'' | ''Author: Gabriel Carroll, USA'' | ||

+ | |||

+ | == Solution == | ||

+ | |||

+ | Suppose such function <math>g</math> exist then: | ||

+ | |||

+ | Lemma 1) <math>g(m) \ne 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 | ||

+ | |||

+ | but <math>\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</math>. | ||

+ | |||

+ | A square cannot be between 2 consecutive squares. Contradiction. Thus, <math>g(m) \ne g(m+1)</math> | ||

+ | |||

+ | |||

+ | <br /> | ||

+ | 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>. | ||

+ | |||

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

+ | |||

+ | <br /> | ||

+ | If <math>a=1</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> | ||

+ | |||

+ | |||

+ | <br /> | ||

+ | |||

+ | If <math>a>1</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> | ||

+ | |||

+ | <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(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. |

## Revision as of 23:35, 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 an such that

, where is not divisible by

If .

Consider an such 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.