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 [[ | + | 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
Contents
[hide]Problem
(Mohsen Jamali, Iran)
A function from the set of positive integers
to itself is such that for all
the number
is divisible by
. Prove that
for each
.
Comment by the proposer. A possible version of this question is:
Find all functions such that for all
, the number
is divisible by
.
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, denotes
, in this context it is clear that it means
.
Solutions
Solution 1
Lemma 1. .
Proof. We must have . But for any integer
,
, so we must have
. ∎
Lemma 2. For all natural ,
, with equality only when
.
Proof. We note that divides
. But if
, then
, a contradiction. Now, if
, then we must have
; since
,
, so we know that
. ∎
Lemma 3. For any prime ,
.
Proof. We know . Since
is positive, either
, or
. But
, so by Lemma 2,
. ∎
Now, for any natural number and any natural number
that is one less than a prime, we have
. But for some integer
,
![$\displaystyle (k^2 + n)^2 = \{[k^2 + f(n]+[n-f(n)]\}^2 = A[k^2 + f(n)] + [n-f(n)]^2$](http://latex.artofproblemsolving.com/0/1/d/01da59a7f55e9aa25e9dd7aec58acaae15736f64.png)
Hence . This means that
has infinitely many divisors, i.e., it is equal to zero. Hence for all natural
,
.
Solution 2
We use Lemmata 1–3 of the previous solution.
For natural , we define
to be product of all primes less than or equal to
.
Lemma 4. For all ,
.
Proof. We will use strong induction. We note that , and
, and
, so
. Now, for all integers
,

This establishes our base case. Now, for , suppose that the lemma holds for all integers
. By Bertrand's Postulate, there exists a prime
greater than
and less than or equal to
. Thus
.
Thus our lemma holds by strong induction. ∎
We will now prove that for all natural ,
.
If this is not true, then there is a least for which this is not true.
Lemma 5. If exists, then it is not prime.
Proof. Suppose the contrary. One of the numbers must be divisible by
. But since
must divide
, none of which can be divisible by
, we conclude that
and hence
. Furthermore, for any prime
,
cannot be divisible by
, since it is a divisor of
, which is not divisible by
, so
. Since
, it follows that
is the only prime divisor of
and again since
,
, a contradiction. ∎
Lemma 6. If exists, then none of the numbers
is prime.
Proof. Suppose, on the contrary, that is prime, for some integer
. We know
. But since
, we must have
, which implies
, a contradiction. ∎
We now claim that does not exist. Since neither
nor
may be prime (by Lemmata 5 and 3), the only possibilities for
are 8, 9, 14, and 15. But
,
,
, and
are all prime, by Lemma 6, we conclude that
. But for each prime
less than
, one of the numbers
![$[f(n_0)]^2+1, \ldots, [f(n_0)]^2 + p$](http://latex.artofproblemsolving.com/6/8/4/684b026415b8a25f8aaba34d9cb1cf3993015881.png)
must be divisible by . Since these divide
, the only one of these which can be divisible by
is
, where
is the integer between 1 and
such that
. It follows that for all primes
less than
,
![$[f(n_0)]^2 \equiv n_0^2 \pmod{p}$](http://latex.artofproblemsolving.com/a/b/5/ab5ce8d89d0fcd1076a91a4df13974276ff76270.png)
By the Chinese Remainder Theorem, then,
![$[f(n_0)]^2 \equiv n_0^2 \pmod{\varpi(n_0)}$](http://latex.artofproblemsolving.com/a/b/b/abb709d3fda09c05fbef106ae1e063a4d094926f.png)
But by Lemma 4, the only solutions to this congruence other than are negative numbers (which are clearly impossible), and solutions which imply
. But by Lemma 2, this implies
, a contradiction. Thus
does not exist, so there is no integer
such that
. Q.E.D.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.