Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

m
m
 
(4 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 />
 +
 +
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 22:53, 23 October 2010

Problem

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

Solution

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}$. 

$(g(m)+n)(g(n)+m)=(n+m+k)^2$

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2010_IMO_Problems/Problem_3&oldid=35949"