Difference between revisions of "2012 USAMO Problems/Problem 3"
(→Solution that involves a non-elementary result) |
|||
Line 27: | Line 27: | ||
Let <math>a_1=1</math>. If <math>2Q>n</math>, then let <math>a_x = 1</math> for all prime numbers <math>x<Q</math>, and <math>a_{xy}=a_xa_y</math>, then (*) becomes: | Let <math>a_1=1</math>. If <math>2Q>n</math>, then 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> Pa_P + Qa_Q = C_1</cmath> |
If <math>2Q\le n</math> but <math>3Q > n</math>, then 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: | If <math>2Q\le n</math> but <math>3Q > n</math>, then 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: | ||
Line 35: | Line 35: | ||
or | or | ||
− | <cmath> Pa_P - Qa_Q = C_2 | + | <cmath> Pa_P - Qa_Q = C_2</cmath> |
If <math>3Q\le n</math>, 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: | If <math>3Q\le n</math>, 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: | ||
Line 42: | Line 42: | ||
or | or | ||
− | <cmath> Pa_P + Qa_Q = C_3 | + | <cmath> Pa_P + Qa_Q = C_3</cmath> |
In each of (1), (2), (3), there exists non zero integers <math>a_P</math> and <math>a_Q</math> which satisfy the equation. Then for other primes <math>p > P</math>, just let <math>a_p=1</math> (or any number). | In each of (1), (2), (3), there exists non zero integers <math>a_P</math> and <math>a_Q</math> which satisfy the equation. Then for other primes <math>p > P</math>, just let <math>a_p=1</math> (or any number). | ||
Line 50: | Line 50: | ||
<cmath>a_k + 2 a_{2k} + \cdots n a_{nk} = a_k (1 + 2 a_2 + \cdots n a_n ) = 0 </cmath> | <cmath>a_k + 2 a_{2k} + \cdots n a_{nk} = a_k (1 + 2 a_2 + \cdots n a_n ) = 0 </cmath> | ||
− | 21: | + | --[[User:Lightest|Lightest]] 21:24, 2 May 2012 (EDT) |
{{solution}} | {{solution}} |
Revision as of 20:24, 2 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.
In the following construction, I am using Bertrand's Theorem without proof. The Theorem states that, for any integer , there exists a prime
such that
.
In other words, 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
So, for , let the largest two primes not larger than
are
and
, and that
. By the Theorem stated above, one can conclude that
, and that
. Using this fact, I'm going to construct the sequence
.
Let . If
, then let
for all prime numbers
, and
, then (*) becomes:
If but
, then let
, and
for all prime numbers
, and
, then (*) becomes:
or
If , let
,
, and
for all prime numbers
, and
, then (*) becomes:
or
In each of (1), (2), (3), there exists non zero integers and
which satisfy the equation. Then for other primes
, just let
(or any number).
This construction is correct because, for any ,
--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 |