Difference between revisions of "2012 USAMO Problems/Problem 3"
(Created page with "==Problem== Determine which integers <math>n > 1</math> have the property that there exists an infinite sequence <math>a_1</math>, <math>a_2</math>, <math>a_3</math>, <math>\dots...") |
m (Changed to "Bertrand's Postulate", as "Bertrand's Theorem" refers to something unrelated) |
||
(23 intermediate revisions by 6 users not shown) | |||
Line 4: | Line 4: | ||
holds for every positive integer <math>k</math>. | holds for every positive integer <math>k</math>. | ||
− | ==Solution== | + | ==Partial Solution== |
+ | For <math>n</math> equal to any odd prime <math>p</math>, the sequence <math>\left\{a_i = \left(\frac{1-n}{2}\right)^{m_p\left(i\right)}\right\}</math>, where <math>p^{m_p\left(i\right)}</math> is the greatest power of <math>p</math> that divides <math>i</math>, gives a valid sequence. Therefore, the set of possible values for <math>n</math> 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 <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. | ||
+ | |||
+ | We proceed to prove that the infinite sequence exists for all <math>n\ge 3</math>. | ||
+ | |||
+ | First, one notices that if we have <math>a_{xy} = a_x a_y</math> for any integers <math>x</math> and <math>y</math>, then it is suffice to define all <math>a_x</math> for <math>x</math> prime, and one only needs to verify the equation (*) | ||
+ | |||
+ | <cmath>a_1+2a_2+\cdots+na_n=0</cmath> | ||
+ | |||
+ | for the other equations will be automatically true. | ||
+ | |||
+ | 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 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>. | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | 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: (i) <math>Q>\frac{n}{2}</math>, (ii) <math>\frac{n}{2} \ge Q > \frac{n}{3}</math>, and (iii) <math>\frac{n}{3} \ge Q > \frac{n}{4}</math>. | ||
+ | |||
+ | Case (i): <math>2Q>n</math>. Let <math>a_x = 1</math> for all prime numbers <math>x<Q</math>, and <math>a_{xy}=a_xa_y</math>, then (*) becomes: | ||
+ | |||
+ | <cmath> Pa_P + Qa_Q = C_1</cmath> | ||
+ | |||
+ | Case (ii): <math>2Q\le n</math> but <math>3Q > n</math>. In this case, let <math>a_2=-1</math>, and <math>a_x = 1</math> for all prime numbers <math>2<x<Q</math>, and <math>a_{xy}=a_xa_y</math>, then (*) becomes: | ||
+ | |||
+ | <cmath> Pa_P + Qa_Q - Qa_{2Q} = C_2 </cmath> | ||
+ | |||
+ | or | ||
+ | |||
+ | <cmath> Pa_P - Qa_Q = C_2</cmath> | ||
+ | |||
+ | Case (iii): <math>3Q\le n</math>. In this case, let <math>a_2=3</math>, <math>a_3=-2</math>, and <math>a_x = 1</math> for all prime numbers <math>3<x<Q</math>, and <math>a_{xy}=a_xa_y</math>, then (*) becomes: | ||
+ | |||
+ | <cmath> Pa_P + Qa_Q + 3Qa_{2Q} - 2Qa_{3Q} = C_3 </cmath> | ||
+ | |||
+ | or | ||
+ | <cmath> Pa_P + Qa_Q = C_3</cmath> | ||
+ | |||
+ | In each case, by Bezout's Theorem, there exists non zero integers <math>a_P</math> and <math>a_Q</math> which satisfy the equation. For all other primes <math>p > P</math>, just let <math>a_p=1</math> (or any other non-zero integer). | ||
+ | |||
+ | This construction is correct because, for any <math>k> 1</math>, | ||
+ | |||
+ | <cmath>a_k + 2 a_{2k} + \cdots n a_{nk} = a_k (1 + 2 a_2 + \cdots n a_n ) = 0 </cmath> | ||
+ | |||
+ | Since Bertrand's Theorem is not elementary, we still need to wait for a better proof. | ||
+ | |||
+ | --[[User:Lightest|Lightest]] 21:24, 2 May 2012 (EDT) | ||
==See Also== | ==See Also== | ||
+ | *[[USAMO Problems and Solutions]] | ||
+ | |||
{{USAMO newbox|year=2012|num-b=2|num-a=4}} | {{USAMO newbox|year=2012|num-b=2|num-a=4}} | ||
+ | {{MAA Notice}} | ||
+ | |||
+ | [[Category:Olympiad Number Theory Problems]] |
Latest revision as of 06:38, 27 October 2022
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.