Difference between revisions of "2012 USAMO Problems/Problem 3"
(→See Also) |
m (Changed to "Bertrand's Postulate", as "Bertrand's Theorem" refers to something unrelated) |
||
(6 intermediate revisions by one other user not shown) | |||
Line 9: | Line 9: | ||
==Solution that involves a non-elementary result== | ==Solution that involves a non-elementary result== | ||
+ | |||
+ | (Since Bertrand's is well known and provable using elementary techniques, I see nothing wrong with this-tigershark22) | ||
+ | |||
For <math>n=2</math>, <math> |a_1| = 2 |a_2| = \cdots = 2^m |a_{2^m}| </math> implies that for any positive integer <math>m</math>, <math>|a_1| \ge 2^m</math>, which is impossible. | For <math>n=2</math>, <math> |a_1| = 2 |a_2| = \cdots = 2^m |a_{2^m}| </math> implies that for any positive integer <math>m</math>, <math>|a_1| \ge 2^m</math>, which is impossible. | ||
Line 21: | Line 24: | ||
To proceed with the construction, I need the following fact: for any positive integer <math>m>2</math>, there exists a prime <math>p</math> such that <math>\frac{m}{2} <p \le m</math>. | To proceed with the construction, I need the following fact: for any positive 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 | + | To prove this, I am going to use '''Bertrand's Postulate''' ([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>. |
Line 58: | Line 61: | ||
--[[User:Lightest|Lightest]] 21:24, 2 May 2012 (EDT) | --[[User:Lightest|Lightest]] 21:24, 2 May 2012 (EDT) | ||
− | |||
− | |||
==See Also== | ==See Also== |
Latest revision as of 05:38, 27 October 2022
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
(Since Bertrand's is well known and provable using elementary techniques, I see nothing wrong with this-tigershark22)
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 Postulate ([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: (i) , (ii) , and (iii) .
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 other non-zero integer).
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)
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.