Difference between revisions of "2012 USAMO Problems/Problem 3"

Revision as of 22:16, 10 July 2020

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=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 Theorem ([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)

Solution 2 (Bezout)

I claim that when $n\geq 3$ there exists an infinite sequence $a_i$ satisfying the given condition.

n=2: Since $a_1=(-2)^k*a_k$ , we have that $|a_1|$ has no upper bound and thus no sequence exists.

n=4: Let $a_i=(-1)^{j+k}$ where $j$ is the number of factors of 2 in $i$ and $k$ is the number of factors of 3 in $i$

n=odd: Let $a_i=(\frac{-n+1}{2})^j$ where $j$ is the number of factors of $n$ in $i$ .

n=even $>$ 4: Let $b$ be either $n-3$ or $n-1$ such that $b$ is not 0 mod 3. For $n=6$ we have $b=5>n/2$ and for even $n>6$ we have $b\geq n-3>n/2$ , so $b$ has no multiples except for itself in the numbers 1 through n. Then we get $\gcd(b,3n/2)=1$ and by Bezout we have $x*3n/2+y*b=1$ for nonzero integer $x, y$ . Then let $(3n/2+b-n(n+1)/2)x=x'$ and similarly define $y'$ . Now let $a_i=x'^j*y'^k$ where $j$ is the number of factors of $n/2$ in $i$ and $k$ is the number of factors of $b$ in $i$ .

We can check that this indeed satisfies the problem conditions. For $n=4$ , note that all the $(a_k, a_{2k}, a_{3k}, a_{4k})$ are $(1,-1,-1,1)$ , and $1-2-3+4=0$ . Similarly, for odd $n$ , we have $(a_k,a_{2k},...a_{nk})$ is $(c, c, c,...,\frac{-n+1}{2}c)$ which adds up to $cn(n-1)/2-cn(n-1)/2=0$ . Note that $(a_k,a_{2k},...a_{nk})$ is $(c, c, c,..., x'c, c, c,..., y', x'c)$ or $(c, c, c,..., x'c, c, c,..., y', c, c, x'c)$ depending on whether $b$ is $n-3$ or $n-1$ , and where the first $x'c$ is located at $a_{\frac{nk}{2}}$ . We can check that this adds up to $c(n(n+1)/2-n/2-n-b+3nx'/2+by')=c(n(n+1)/2-3n/2-b+3n/2+b-n(n+1)/2)=0$ .

-tigershark22

@@ Line 59: / Line 59: @@
 --[[User:Lightest|Lightest]] 21:24, 2 May 2012 (EDT)
-{{solution}}
+==Solution 2 (Bezout)==
+I claim that when <math>n\geq 3</math> there exists an infinite sequence <math>a_i</math> satisfying the given condition.
+n=2: Since <math>a_1=(-2)^k*a_k</math>, we have that <math>|a_1|</math> has no upper bound and thus no sequence exists.
+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=even<math>></math>4: Let <math>b</math> be either <math>n-3</math> or <math>n-1</math> such that <math>b</math> is not 0 mod 3. For <math>n=6</math> we have <math>b=5>n/2</math> and for even <math>n>6</math> we have <math>b\geq n-3>n/2</math>, so <math>b</math> has no multiples except for itself in the numbers 1 through n. Then we get <math>\gcd(b,3n/2)=1</math> and by Bezout we have <math>x*3n/2+y*b=1</math> for nonzero integer <math>x, y</math>. Then let <math>(3n/2+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/2</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> 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,..., x'c, c, c,..., y', x'c)</math> or <math>(c, c, c,..., x'c, c, c,..., y', c, c, x'c)</math> depending on whether <math>b</math> is <math>n-3</math> or <math>n-1</math>, and where the first <math>x'c</math> is located at <math>a_{\frac{nk}{2}}</math>. We can check that this adds up to <math>c(n(n+1)/2-n/2-n-b+3nx'/2+by')=c(n(n+1)/2-3n/2-b+3n/2+b-n(n+1)/2)=0</math>.
+-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

Page

Toolbox

Search