Difference between revisions of "2012 USAMO Problems/Problem 3"
Tigershark22 (talk | contribs) (→Solution 2 (Bezout)) |
Tigershark22 (talk | contribs) (→Solution 2 (Bezout)) |
||
Line 69: | Line 69: | ||
n=4: Let <math>a_i=(-1)^{j+k}</math> where <math>j</math> is the number of factors of 2 in <math>i</math> and <math>k</math> is the number of factors of 3 in <math>i</math> | n=4: Let <math>a_i=(-1)^{j+k}</math> where <math>j</math> is the number of factors of 2 in <math>i</math> and <math>k</math> is the number of factors of 3 in <math>i</math> | ||
− | n=odd: Let <math>a_i=(\frac{-n+1}{2})^j</math> where <math>j</math> is the number of factors of <math>n</math> in <math>i</math>. | + | n=odd: Let <math>a_i=(\frac{-n+1}{2})^j</math> where <math>j</math> is the number of factors of <math>n</math> in <math>i</math> (that is, the maximum number <math>j</math> such that <math>\frac{i}{n^j}</math> is an integer). |
− | n=even<math>></math>4: Let <math>b | + | n=even<math>></math>4: Let <math>b=n-1</math>.We have <math>b>n/2</math>, so <math>b</math> has no multiples except for itself in the numbers 1 through n. Also we get <math>\gcd(b,n)=\gcd(1,n)=1</math>. |
− | We can check that this indeed satisfies the problem conditions. For <math>n=4</math>, note that all the <math>(a_k, a_{2k}, a_{3k}, a_{4k})</math> are <math>(1,-1,-1,1)</math>, and <math>1-2-3+4=0</math>. Similarly, for odd <math>n</math>, we have <math>(a_k,a_{2k},...a_{nk})</math> is <math>(c, c, c,...,\frac{-n+1}{2}c)</math> which adds up to <math>cn(n-1)/2-cn(n-1)/2=0</math>. Note that <math>(a_k,a_{2k},...a_{nk})</math> is <math>(c, c, c,..., | + | By Bezout we have <math>x*n+y*b=1</math> for nonzero integer <math>x, y</math>. Then let <math>(n+b-n(n+1)/2)x=x'</math> and similarly define <math>y'</math>. Now let <math>a_i=x'^j*y'^k</math> where <math>j</math> is the number of factors of <math>n</math> in <math>i</math> and <math>k</math> is the number of factors of <math>b</math> in <math>i</math>. |
+ | |||
+ | We can check that this indeed satisfies the problem conditions. For <math>n=4</math>, note that all the <math>(a_k, a_{2k}, a_{3k}, a_{4k})</math> are <math>(1,-1,-1,1)</math>, and <math>1-2-3+4=0</math>. | ||
+ | |||
+ | Similarly, for odd <math>n</math>, we have <math>(a_k,a_{2k},...a_{nk})</math> is <math>(c, c, c,...,\frac{-n+1}{2}c)</math> for some c by using the construction, for which <math>S=a_k+2a_{2k}+...+na_{nk}</math> adds up to <math>S=cn(n-1)/2-cn(n-1)/2=0</math>. | ||
+ | |||
+ | Note that for even <math>n</math>, we have <math>(a_k,a_{2k},...a_{nk})</math> is <math>(c, c, c,..., y'c, x'c)</math> or <math>(c, c, c,..., y'c, c, c, x'c)</math> for some c by construction. We can check that this adds up to <math>S=c(n(n+1)/2-n-b+nx'+by')=c(n(n+1)/2-n-b+n+b-n(n+1)/2)=0</math>. | ||
-tigershark22 | -tigershark22 |
Revision as of 09:54, 11 July 2020
Contents
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: (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)
Solution 2 (Bezout)
Motivation: The condition that it must work for all positive integers is annoying. Thus, we construct the sequence so that the integers
through
are all a multiple of the original
through
.
I claim that when there exists an infinite sequence
satisfying the given condition.
n=2: Since , we have that
has no upper bound and thus no sequence exists.
n=4: Let where
is the number of factors of 2 in
and
is the number of factors of 3 in
n=odd: Let where
is the number of factors of
in
(that is, the maximum number
such that
is an integer).
n=even4: Let
.We have
, so
has no multiples except for itself in the numbers 1 through n. Also we get
.
By Bezout we have for nonzero integer
. Then let
and similarly define
. Now let
where
is the number of factors of
in
and
is the number of factors of
in
.
We can check that this indeed satisfies the problem conditions. For , note that all the
are
, and
.
Similarly, for odd , we have
is
for some c by using the construction, for which
adds up to
.
Note that for even , we have
is
or
for some c by construction. We can check that this adds up to
.
-tigershark22
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.