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 "2004 IMO Shortlist Problems/N3"

(nice solution + that thing)
 
m (→‎Solution 2: typo)
 
Line 46: Line 46:
 
''Proof.''  We will use strong induction.  We note that <math> \displaystyle 2 \cdot 5 \cdot 7 \cdot 11 = 770 > 2\cdot 18^2 </math>, and <math> \displaystyle 3 \cdot 13 > 18 </math>, and <math> \displaystyle 17 > 18/2 </math>, so <math> \displaystyle \varpi(18) = \varpi(17) > 18^4 > 17^4 </math>.  Now, for all integers <math> 19 \le n \le 36 </math>, <center><math> \varpi(n) \ge 19 \cdot \varpi(17) > 2^4 \cdot \pi(17) > 2^4\cdot 18^4 = 36^4 \ge n^4 </math>.</center>
 
''Proof.''  We will use strong induction.  We note that <math> \displaystyle 2 \cdot 5 \cdot 7 \cdot 11 = 770 > 2\cdot 18^2 </math>, and <math> \displaystyle 3 \cdot 13 > 18 </math>, and <math> \displaystyle 17 > 18/2 </math>, so <math> \displaystyle \varpi(18) = \varpi(17) > 18^4 > 17^4 </math>.  Now, for all integers <math> 19 \le n \le 36 </math>, <center><math> \varpi(n) \ge 19 \cdot \varpi(17) > 2^4 \cdot \pi(17) > 2^4\cdot 18^4 = 36^4 \ge n^4 </math>.</center>
  
−
This establishes our base case.  Now, for <math> \displaystyle n > 36 </math>, suppose that the lemma holds for all integers <math> 17 \le k \le n-1 </math>.  By [[Bertand's Postulate]], there exists a prime <math> \displaystyle p_1 </math> greater than <math> \lceil n/2 \rceil </math> and less than or equal to <math> \displaystyle n </math>.  Thus
+
This establishes our base case.  Now, for <math> \displaystyle n > 36 </math>, suppose that the lemma holds for all integers <math> 17 \le k \le n-1 </math>.  By [[Bertrand's Postulate]], there exists a prime <math> \displaystyle p_1 </math> greater than <math> \lceil n/2 \rceil </math> and less than or equal to <math> \displaystyle n </math>.  Thus
 
<center>
 
<center>
 
<math> \varpi(n) \ge p_1 \cdot \varpi(\lceil n/2 \rceil) > p_1 \cdot (\lceil n/2 \rceil)^4 \ge p_1 \cdot (n/2)^4 > n/2 \cdot (n/2)^4 > 16 \cdot (n/2)^4 = n^4 </math>.
 
<math> \varpi(n) \ge p_1 \cdot \varpi(\lceil n/2 \rceil) > p_1 \cdot (\lceil n/2 \rceil)^4 \ge p_1 \cdot (n/2)^4 > n/2 \cdot (n/2)^4 > 16 \cdot (n/2)^4 = n^4 </math>.
Line 74: Line 74:
  
 
{{alternate solutions}}
 
{{alternate solutions}}
−
 
  
 
== Resources ==
 
== Resources ==

Latest revision as of 14:42, 13 June 2007

Problem

(Mohsen Jamali, Iran) A function $\displaystyle f$ from the set of positive integers $\mathbf{N}$ to itself is such that for all $m, n \in \mathbf{N}$ the number $\displaystyle (m^2 +n)^2$ is divisible by $\displaystyle f^2(m) + f(n)$. Prove that $\displaystyle f(n) = n$ for each $n \in \mathbf{N}$.


Comment by the proposer. A possible version of this question is:

Find all functions $f : \mathbf{N}\rightarrow \mathbf{N}$ such that for all $m,n \in \mathbf{N}$, the number $\displaystyle (m^2 +n)^2$ is divisible by $\displaystyle f^2(m) + f(n)$.


This alternative form was also Problem 3 of the 2005 5th Romanian TST, Problem 1 of the 3rd independent study of the 2005 3rd Taiwan TST, and Problem 3 of the 2005 French Mathematical Olympiad, Dossier 4.

Note: Although strictly speaking, $\displaystyle f^2(x)$ denotes $\displaystyle f(f(x))$, in this context it is clear that it means $\displaystyle [f(x)]^2$.

Solutions

Solution 1

Lemma 1. $\displaystyle f(1) = 1$.

Proof. We must have $[f(1)]^2 + f(1) \mid (1^2+1)^2 = 4$. But for any integer $\displaystyle y > 1$, $y^2 + y \ge 6$, so we must have $\displaystyle f(1) = 1$. ∎

Lemma 2. For all natural $\displaystyle n$, $f(n) \le n^2$, with equality only when $\displaystyle n=1$.

Proof. We note that $\displaystyle [f(n)]^2 + f(1) = [f(n)]^2 + 1$ divides $\displaystyle (n^2+1)^2$. But if $f(n) \ge n^2+1$, then $\displaystyle [f(n)]^2 + 1 > (n^2 + 1)^2$, a contradiction. Now, if $\displaystyle n>1$, then we must have $\displaystyle f(n) + 1 \mid (n+1)^2$; since $\displaystyle (n+1)^2/2 < n^2 + 1 < (n+1)^2$, $n^2 +1 \nmid (n+1)^2$, so we know that $\displaystyle f(n) \neq n^2$. ∎

Lemma 3. For any prime $\displaystyle p$, $\displaystyle f(p-1) = p-1$.

Proof. We know $f(1) + f(p-1) = 1 + f(p-1) \mid p^2$. Since $\displaystyle f(p-1)$ is positive, either $\displaystyle f(p-1) = p-1$, or $\displaystyle f(p-1) = p^2 -1$. But $\displaystyle p^2 -1 > (p-1)^2$, so by Lemma 2, $\displaystyle f(p-1) = p-1$. ∎

Now, for any natural number $\displaystyle n$ and any natural number $\displaystyle k$ that is one less than a prime, we have $[f(k)]^2 + f(n) = k^2 + f(n) \mid (k^2 + n)^2$. But for some integer $\displaystyle A$,

$\displaystyle (k^2 + n)^2 = \{[k^2 + f(n]+[n-f(n)]\}^2 = A[k^2 + f(n)] + [n-f(n)]^2$.

Hence $k^2 + f(n) \mid [n-f(n)]^2$. This means that $\displaystyle [n-f(n)]^2$ has infinitely many divisors, i.e., it is equal to zero. Hence for all natural $\displaystyle n$, $\displaystyle f(n) = n$.


Solution 2

We use Lemmata 1–3 of the previous solution.

For natural $\displaystyle n$, we define $\displaystyle \varpi(n)$ to be product of all primes less than or equal to $\displaystyle n$.

Lemma 4. For all $n\ge 17$, $\displaystyle \varpi(n) > n^4$.

Proof. We will use strong induction. We note that $\displaystyle 2 \cdot 5 \cdot 7 \cdot 11 = 770 > 2\cdot 18^2$, and $\displaystyle 3 \cdot 13 > 18$, and $\displaystyle 17 > 18/2$, so $\displaystyle \varpi(18) = \varpi(17) > 18^4 > 17^4$. Now, for all integers $19 \le n \le 36$,

$\varpi(n) \ge 19 \cdot \varpi(17) > 2^4 \cdot \pi(17) > 2^4\cdot 18^4 = 36^4 \ge n^4$.

This establishes our base case. Now, for $\displaystyle n > 36$, suppose that the lemma holds for all integers $17 \le k \le n-1$. By Bertrand's Postulate, there exists a prime $\displaystyle p_1$ greater than $\lceil n/2 \rceil$ and less than or equal to $\displaystyle n$. Thus

$\varpi(n) \ge p_1 \cdot \varpi(\lceil n/2 \rceil) > p_1 \cdot (\lceil n/2 \rceil)^4 \ge p_1 \cdot (n/2)^4 > n/2 \cdot (n/2)^4 > 16 \cdot (n/2)^4 = n^4$.

Thus our lemma holds by strong induction. ∎

We will now prove that for all natural $\displaystyle n$, $\displaystyle f(n) = n$.

If this is not true, then there is a least $\displaystyle n_0$ for which this is not true.

Lemma 5. If $\displaystyle n_0$ exists, then it is not prime.

Proof. Suppose the contrary. One of the numbers $[f(n_0)]^2, [f(n_0)]^2 + 1, \ldots, [f(n_0)]^2 + n_0 -1$ must be divisible by $\displaystyle n_0$. But since $[f(n_0)]^2 +1 ,\ldots, [f(n_0)]^2 + n_0-1$ must divide ${} (n_0^2+1)^2, \ldots, (n_0^2+n_0-1)^2$, none of which can be divisible by $\displaystyle n_0$, we conclude that $n_0 \mid [f(n_0)]^2$ and hence $n_0 \mid f(n_0)$. Furthermore, for any prime $\displaystyle p< n_0$, $\displaystyle [f(n_0)]^2+p$ cannot be divisible by $\displaystyle p$, since it is a divisor of $\displaystyle (n_0^2+p)^2$, which is not divisible by $\displaystyle p$, so $p \nmid f(n_0)$. Since $\displaystyle f(n_0) < n_0^2$, it follows that $\displaystyle n_0$ is the only prime divisor of $\displaystyle f(n_0)$ and again since $\displaystyle f(n_0) < n_0^2$, $\displaystyle f(n_0) = n_0$, a contradiction. ∎

Lemma 6. If $\displaystyle n_0$ exists, then none of the numbers $n_0^2+1, \ldots, n_0^2 + n_0 -1$ is prime.

Proof. Suppose, on the contrary, that $\displaystyle n_0^2 + k$ is prime, for some integer $1 \le k \le n_0-1$. We know $[f(n_0)]^2 + k \mid p^2$. But since $\displaystyle 1< [f(n_0)]^2 +k < n_0^4 + k < (n_0^2+k)^2 = p^2$, we must have $\displaystyle [f(n_0)]^2 +k = n_0^2 + k$, which implies $\displaystyle f(n_0) = n_0$, a contradiction. ∎

We now claim that $\displaystyle n_0$ does not exist. Since neither $\displaystyle n_0$ nor $\displaystyle n_0+1$ may be prime (by Lemmata 5 and 3), the only possibilities for $\displaystyle n_0 < 17$ are 8, 9, 14, and 15. But $\displaystyle 8^2 + 3 = 67$, $\displaystyle 9^2 + 8 = 89$, $\displaystyle 14^2+1 = 197$, and $\displaystyle 15^2 +2 = 227$ are all prime, by Lemma 6, we conclude that $n\ge 17$. But for each prime $\displaystyle p$ less than $\displaystyle n_0$, one of the numbers

$[f(n_0)]^2+1, \ldots, [f(n_0)]^2 + p$

must be divisible by $\displaystyle p$. Since these divide $(n_0^2 + 1)^2, \ldots, (n_0^2 + p)^2$, the only one of these which can be divisible by $\displaystyle p$ is $\displaystyle [f(n_0)]^2 + k$, where $\displaystyle k$ is the integer between 1 and $\displaystyle p$ such that $k \equiv -n_0^2 \pmod{p}$. It follows that for all primes $\displaystyle p$ less than $\displaystyle n$,

$[f(n_0)]^2 \equiv n_0^2 \pmod{p}$.

By the Chinese Remainder Theorem, then,

$[f(n_0)]^2 \equiv n_0^2 \pmod{\varpi(n_0)}$.

But by Lemma 4, the only solutions to this congruence other than $\displaystyle [f(n_0)]^2 = n_0^2$ are negative numbers (which are clearly impossible), and solutions which imply $\displaystyle [f(n_0)^2] > n^2 + n^4$. But by Lemma 2, this implies $\displaystyle n^4 > [f(n_0)]^2 > n^2 + n^4$, a contradiction. Thus $\displaystyle n_0$ does not exist, so there is no integer $\displaystyle n$ such that $\displaystyle f(n) \neq n$. Q.E.D.


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2004_IMO_Shortlist_Problems/N3&oldid=15222"