Difference between revisions of "2012 USAMO Problems/Problem 3"
(→Solution that involves a non-elementary result) |
(→Solution that involves a non-elementary result) |
||
Line 23: | Line 23: | ||
To prove this, I am going to use '''Bertrand's Theorem''' ([http://en.wikipedia.org/wiki/Bertrand's_postulate]) without proof. The Theorem states that, for any integer <math>n>1</math>, there exists a prime <math>p</math> such that <math>n<p\le 2n-1</math>. In other words, for any positive integer <math>m>2</math>, if <math>m=2n</math> with <math>n>1</math>, then there exists a prime <math>p</math> such that <math>\frac{m}{2} < p < m</math>, and if <math>m=2n-1</math> with <math>n>1</math>, then there exists a prime <math>p</math> such that <math>\frac{m+1}{2} <p\le m</math>, both of which guarantees that for any integer <math>m>2</math>, there exists a prime <math>p</math> such that <math>\frac{m}{2} <p \le m</math>. | To prove this, I am going to use '''Bertrand's Theorem''' ([http://en.wikipedia.org/wiki/Bertrand's_postulate]) without proof. The Theorem states that, for any integer <math>n>1</math>, there exists a prime <math>p</math> such that <math>n<p\le 2n-1</math>. In other words, for any positive integer <math>m>2</math>, if <math>m=2n</math> with <math>n>1</math>, then there exists a prime <math>p</math> such that <math>\frac{m}{2} < p < m</math>, and if <math>m=2n-1</math> with <math>n>1</math>, then there exists a prime <math>p</math> such that <math>\frac{m+1}{2} <p\le m</math>, both of which guarantees that for any integer <math>m>2</math>, there exists a prime <math>p</math> such that <math>\frac{m}{2} <p \le m</math>. | ||
− | + | ||
+ | |||
+ | |||
+ | Go back to the problem. Suppose <math>n\ge 3</math>. Let the largest two primes not larger than <math>n</math> are <math>P</math> and <math>Q</math>, and that <math>n\ge P > Q</math>. By the fact stated above, one can conclude that <math>2P > n</math>, and that <math>4Q = 2(2Q) \ge 2P > n</math>. Let's construct <math>a_n</math>: | ||
Let <math>a_1=1</math>. There will be three cases: <math>Q>\frac{n}{2}</math>, <math> \frac{n}{2} \ge Q > \frac{n}{3}</math>, and <math>\frac{n}{3} \ge Q > \frac{n}{4}</math>. | Let <math>a_1=1</math>. There will be three cases: <math>Q>\frac{n}{2}</math>, <math> \frac{n}{2} \ge Q > \frac{n}{3}</math>, and <math>\frac{n}{3} \ge Q > \frac{n}{4}</math>. |
Revision as of 15:30, 3 May 2012
Contents
[hide]Problem
Determine which integers have the property that there exists an infinite sequence
,
,
,
of nonzero integers such that the equality
holds for every positive integer
.
Partial Solution
For equal to any odd prime
, the sequence
, where
is the greatest power of
that divides
, gives a valid sequence. Therefore, the set of possible values for
is at least the set of odd primes.
Solution that involves a non-elementary result
For ,
implies that for any positive integer
,
, which is impossible.
We proceed to prove that the infinite sequence exists for all .
First, one notices that if we have for any integers
and
, then it is suffice to define all
for
prime, and one only needs to verify the equation (*)
for the other equations will be automatically true.
To proceed with the construction, I need the following fact: for any positive integer , there exists a prime
such that
.
To prove this, I am going to use Bertrand's Theorem ([1]) without proof. The Theorem states that, for any integer , there exists a prime
such that
. In other words, for any positive integer
, if
with
, then there exists a prime
such that
, and if
with
, then there exists a prime
such that
, both of which guarantees that for any integer
, there exists a prime
such that
.
Go back to the problem. Suppose . Let the largest two primes not larger than
are
and
, and that
. By the fact stated above, one can conclude that
, and that
. Let's construct
:
Let . There will be three cases:
,
, and
.
Case (i): . Let
for all prime numbers
, and
, then (*) becomes:
Case (ii): but
. In this case, let
, and
for all prime numbers
, and
, then (*) becomes:
or
Case (iii): . In this case, let
,
, and
for all prime numbers
, and
, then (*) becomes:
or
In each case, by Bezout's Theorem, there exists non zero integers and
which satisfy the equation. For all other primes
, just let
(or any number).
This construction is correct because, for any ,
Since Bertrand's Theorem is not elementary, we still need to wait for a better proof.
--Lightest 21:24, 2 May 2012 (EDT)
This problem needs a solution. If you have a solution for it, please help us out by adding it.
See Also
2012 USAMO (Problems • Resources) | ||
Preceded by Problem 2 |
Followed by Problem 4 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |