2012 USAMO Problems/Problem 3

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

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 (*)$

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 $n>1$ , there exists a prime $p$ such that $n<p\le 2n-1$ .

In other words, if $m=2n$ with $n>1$ , then there exists a prime $p$ such that $m/2 < p < m$ , and if $m=2n-1$ with $n>1$ , then there exists a prime $p$ such that $(m+1)/2 <p\le m$ , both of which guarantees that for any integer $m>2$ , there exists a prime $p$ such that $m/2 <p \le m$

So, for $n\ge 3$ , let the largest two primes not larger than $n$ are $P$ and $Q$ , and that $n\ge P > Q$ . By the Theorem stated above, one can conclude that $2P > n$ , and that $4Q = 2(2Q) \ge 2P > n$ . Using this fact, I'm going to construct the sequence $a_n$ .

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

$Pa_P + Qa_Q = C_1$

If $2Q\le n$ but $3Q > n$ , then 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$

If $3Q\le n$ , 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 of (1), (2), (3), there exists non zero integers $a_P$ and $a_Q$ which satisfy the equation. Then for other primes $p > P$ , just let $a_p=1$ (or any number).

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$

--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.

2012 USAMO (Problems • Resources)
Preceded by Problem 2	Followed by Problem 4
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search

2012 USAMO Problems/Problem 3

Contents

Problem

Partial Solution

Solution that involves a non-elementary result

See Also