Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2012 USAMO Problems/Problem 3"
m (Changed to "Bertrand's Postulate", as "Bertrand's Theorem" refers to something unrelated)
 
(18 intermediate revisions by 4 users 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.
  
 
We proceed to prove that the infinite sequence exists for all <math>n\ge 3</math>.
 
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  
+
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   (*)</cmath>
+
<cmath>a_1+2a_2+\cdots+na_n=0</cmath>
  
 
for the other equations will be automatically true.
 
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 <math>n>1</math>, there exists a prime <math>p</math> such that <math>n<p\le 2n-1</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 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>.
  
−
In other words, if <math>m=2n</math> with <math>n>1</math>, then there exists a prime <math>p</math> such that <math>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>(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>m/2 <p \le m</math>
 
  
−
So, for <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 Theorem stated above, one can conclude that <math>2P > n</math>, and that <math>4Q = 2(2Q) \ge 2P > n</math>. Using this fact, I'm going to construct the sequence <math>a_n</math>.
 
  
−
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  (1)</cmath>
+
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>:
  
−
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:
+
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>
 
<cmath> Pa_P + Qa_Q - Qa_{2Q} = C_2 </cmath>
Line 35: Line 43:
 
or
 
or
  
−
<cmath> Pa_P - Qa_Q = C_2   (2)</cmath>
+
<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:
+
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>
 
<cmath> Pa_P + Qa_Q + 3Qa_{2Q} - 2Qa_{3Q} = C_3 </cmath>
  
 
or
 
or
−
<cmath> Pa_P + Qa_Q = C_3   (3)</cmath>
+
<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 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>,  
 
This construction is correct because, for any <math>k> 1</math>,  
Line 50: Line 58:
 
<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:22, 2 May 2012 (EDT)
+
Since Bertrand's Theorem is not elementary, we still need to wait for a better proof.
  
−
{{solution}}
+
--[[User:Lightest|Lightest]] 21:24, 2 May 2012 (EDT)
  
 
==See Also==
 
==See Also==
Line 58: Line 66:
  
 
{{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 05:38, 27 October 2022

Problem

Determine which integers $n > 1$ have the property that there exists an infinite sequence $a_1$, $a_2$, $a_3$, $\dots$ of nonzero integers such that the equality \[a_k + 2a_{2k} + \dots + na_{nk} = 0\] holds for every positive integer $k$.

Partial Solution

For $n$ equal to any odd prime $p$, the sequence $\left\{a_i = \left(\frac{1-n}{2}\right)^{m_p\left(i\right)}\right\}$, where $p^{m_p\left(i\right)}$ is the greatest power of $p$ that divides $i$, gives a valid sequence. Therefore, the set of possible values for $n$ 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 $n=2$, $|a_1| = 2 |a_2| = \cdots = 2^m |a_{2^m}|$ implies that for any positive integer $m$, $|a_1| \ge 2^m$, which is impossible.

We proceed to prove that the infinite sequence exists for all $n\ge 3$.

First, one notices that if we have $a_{xy} = a_x a_y$ for any integers $x$ and $y$, then it is suffice to define all $a_x$ for $x$ prime, and one only needs to verify the equation (*)

\[a_1+2a_2+\cdots+na_n=0\]

for the other equations will be automatically true.

To proceed with the construction, I need the following fact: for any positive integer $m>2$, there exists a prime $p$ such that $\frac{m}{2} <p \le m$.

To prove this, I am going to use Bertrand's Postulate ([1]) without proof. The Theorem states that, for any integer $n>1$, there exists a prime $p$ such that $n<p\le 2n-1$. In other words, for any positive integer $m>2$, if $m=2n$ with $n>1$, then there exists a prime $p$ such that $\frac{m}{2} < p < m$, and if $m=2n-1$ with $n>1$, then there exists a prime $p$ such that $\frac{m+1}{2} <p\le m$, both of which guarantees that for any integer $m>2$, there exists a prime $p$ such that $\frac{m}{2} <p \le m$.



Go back to the problem. Suppose $n\ge 3$. Let the largest two primes not larger than $n$ are $P$ and $Q$, and that $n\ge P > Q$. By the fact stated above, one can conclude that $2P > n$, and that $4Q = 2(2Q) \ge 2P > n$. Let's construct $a_n$:

Let $a_1=1$. There will be three cases: (i) $Q>\frac{n}{2}$, (ii) $\frac{n}{2} \ge Q > \frac{n}{3}$, and (iii) $\frac{n}{3} \ge Q > \frac{n}{4}$.

Case (i): $2Q>n$. Let $a_x = 1$ for all prime numbers $x<Q$, and $a_{xy}=a_xa_y$, then (*) becomes:

\[Pa_P + Qa_Q = C_1\]

Case (ii): $2Q\le n$ but $3Q > n$. In this case, let $a_2=-1$, and $a_x = 1$ for all prime numbers $2<x<Q$, and $a_{xy}=a_xa_y$, then (*) becomes:

\[Pa_P + Qa_Q - Qa_{2Q} = C_2\]

or

\[Pa_P - Qa_Q = C_2\]

Case (iii): $3Q\le n$. In this case, let $a_2=3$, $a_3=-2$, and $a_x = 1$ for all prime numbers $3<x<Q$, and $a_{xy}=a_xa_y$, then (*) becomes:

\[Pa_P + Qa_Q + 3Qa_{2Q} - 2Qa_{3Q} = C_3\]

or \[Pa_P + Qa_Q = C_3\]

In each case, by Bezout's Theorem, there exists non zero integers $a_P$ and $a_Q$ which satisfy the equation. For all other primes $p > P$, just let $a_p=1$ (or any other non-zero integer).

This construction is correct because, for any $k> 1$,

\[a_k + 2 a_{2k} + \cdots n a_{nk} = a_k (1 + 2 a_2 + \cdots n a_n ) = 0\]

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2012_USAMO_Problems/Problem_3&oldid=179575"