Determine which integers $n > 1$ have the property that there exists an infinite sequence $a_1, a_2, a_3, \ldots$ of nonzero integers such that the equality \[a_k+2a_{2k}+\ldots+na_{nk}=0\]holds for every positive integer $k$.
Problem
Source: 2012 USAMO problem #3
Tags: function, modular arithmetic, floor function, AMC, USA(J)MO, USAMO
25.04.2012 01:04
Mod edit: Hidden.
25.04.2012 01:11
I had read much of the research around the Erdos discrepancy problem (http://michaelnielsen.org/polymath1/index.php?title=The_Erd%C5%91s_discrepancy_problem) And once you've seen those methods this problem is very straightforward; simply make $a_i$ be completely multiplicative, then take two fairly large primes and bezout and you're done. Amusingly I sent out the EDP link to most of the TSTST group some time ago but I doubt very many people read it. EDIT: apparently Linus Hamilton read the link and instantly made the connection, lol
25.04.2012 01:17
pythag011 wrote: And once you've seen those methods this problem is very straightforward; simply make $a_i$ be completely multiplicative, then take two fairly large primes and bezout and you're done. I hadn't seen this problem before but I think I used the same method. Bertrand's postulate gives us two primes so we can make $a_1, a_2, \hdots, a_n$ multiplicative and also satisfy $a_1 + 2a_2 + \cdots + na_n = 0$. Then extend it to an infinite multiplicative sequence by setting $a_p = 1$ whenever $p$ is a prime bigger than $n$.
25.04.2012 01:21
Apparently mitchell read my link as well~
25.04.2012 01:23
so does this mean it was all n>1?
25.04.2012 01:24
well no n=2 fails lol @pythag011 I didn't read it but I did that
25.04.2012 01:27
It seems like this was the easy part of the problem, but how many points do you guys think I'd get for constructing an answer for the odd numbers and wrongly stating that n=2 worked? (because I included rational numbers in the sequence for n=2 for some strange reason) I'm hoping for 1 but it seems like 0 is more likely.
25.04.2012 01:30
I solved this one but I used the theorem that there is a prime between x and 2x for all positive x. I forgot the name, so I just called it a famous theorem. There goes my chance for a perfect 7 on question 3....
25.04.2012 01:39
pythag011 wrote: And once you've seen those methods this problem is very straightforward; simply make $a_i$ be completely multiplicative, then take two fairly large primes and bezout and you're done. This is exactly what I did, except I haven't seen these ideas. u_u. Anyways, here is a sketch of what I put on the test. The details were not pretty.
GeorgiaTechMan wrote: prime between x and 2x for all positive x Bertrand's Postulate And in fact there's one between $x$ and $2x-2$ for $x \ge 4$. ... So anyways, USAMO2 >> USAMO3? What is this...
25.04.2012 02:06
Isn't Bertrand's Postulate not allowed on USAMO? (according to Romanian AMSP instructors anyway) Since there's no way anyone here really knows how to prove it that is.
25.04.2012 02:07
lab wrote: Isn't Bertrand's Postulate not allowed on USAMO? (according to Romanian AMSP instructors anyway) Since there's no way anyone here really knows how to prove it that is. It's not very hard to prove, just a bit annoying...
25.04.2012 02:21
Err also in general any well-known named result, like Bertrand's postulate, is citable on an Olympiad. It's just that certain such results (like Dirichlet's theorem) may draw the ire of graders. But Bertrand's postulate is not really that high-tech.
25.04.2012 04:02
Here's an ugly solution that I came up with. It is an algorithmic construction. I am still not 100% sure of its validity, so if anyone could check it, that would be great!.
25.04.2012 05:00
oh the fml of not doing math and forgetting bertrand's postulate when i needed it most
25.04.2012 05:08
How may points would this be worth?
25.04.2012 05:14
superpi83 wrote: How may points would this be worth?
I got that construction in about a minute, then gave up on the problem, and walked out expecting 0 points for it. I don't think the graders are particularly interested in the simplest cases, they're probably interested in the multiplicative sequence thing that I failed to see.
25.04.2012 17:22
Seems like everyone's solutions are "unsure" or "not rigorous", so I'll post mine (exactly the same as pythag011's idea)
26.04.2012 15:50
28.01.2017 02:33
About five years later, here is a completed version of the solution I alluded to in 2012.
12.06.2020 04:59
$n=2$ does not hold since $a_1=2^ka_{2^k}$ for any positive integer $k$. We will construct a valid sequence for any $n\ge 3$. In addition, we will make the sequence completely multiplicative. First, we list explicit constructions for small cases $n\le 8$: For $n=3,5,7$, let $a_k = (-\frac{n-1}{2})^{v_n(k)}$. For $n=4$, let $a_k=2^{v_2(k)}(-7)^{v_3(k)}$. For $n=6$, let $a_k=(-3)^{v_3(k)}4^{v_5(k)}$. For $n=8$, let $a_k=(-2)^{v_5(k)+v_7(k)}$. All of them satisfy $a_1+2a_2+\dots +na_n=0$, so they are valid since they are completely multiplicative. For $n\ge 9$, we choose two distinct primes $p<q$ using Bertrand's postulate: - If $n=4m$, let $2m<q<4m$ and $m<p<2m$. - If $n=4m+1$, let $2m+1<q<4m+2$ and $m+1<p<2m+2$. - If $n=4m+2$, let $2m+1<q<4m+2$ and $m+1<p<2m+2$. - If $n=4m+3$, let $2m+2<q<4m+4$ and $m+1<p<2m+2$. In all four cases, $4\le p<q\le n$, $2q>n$, and $4p>n$. Since it suffices to choose values at primes, we let $a_r=1$ for all primes $r$ except $p$ and $q$. The only condition left is \[a_1+2a_2+\dots +na_n=0,\]which is linear in $a_p$ and $a_q$ by our choices of $p$ and $q$. Since $q>6$ and $p>3$, $q$ is coprime with $(1+2+3)p$, so we are done by Bezout.
19.06.2020 03:04
22.06.2020 17:33
We claim that $n$ works iff $n\ge 2$. First, we show that $n=2$ does not satisfy this property. Suppose otherwise; consider some such sequence of $a_i$. Claim: For all $k \ge 1$, $a_1=(-2)^ka_{2^k}$. Solution: Induct on $k$. For the base case, remark that $a_1=-2a_2$ because $a_1+2a_2=0$. For the induction step, note that $a_1 =(-2)^ka_{2^k} = (-2)^k \cdot (-2a_{2^{k+1}}) = (-2)^{k+1}a_{2^{k+1}}$. $\fbox{}$ Remark that this implies that $2^k\mid a_1$ for all $k\ge 1$, absurd because $a_1\ne 0$. Now, we show that all $n\ne 2$ satisfy this property. For convenience, write $a_i=f(i)$. We will find multiplicative $f$ satisfying \[f(1)+2f(2)+\cdots + nf(n)=0,\]which will clearly suffice by multiplicativity. The idea is the following. When $n/4 \ge 2$, we can choose some primes \[\left\lfloor\frac{n}{4}\right\rfloor < q < 2\left\lfloor\frac{n}{4}\right\rfloor \le \left\lceil\frac{n}{2}\right\rceil\]and \[\left\lfloor\frac{n}{2}\right\rfloor < p < 2\left\lfloor\frac{n}{2}\right\rfloor \le n\]by Bertrand's Postulate. As long as $n/4 \ge \sqrt{n}$ (that is, $n \ge 16$), we can then fix $f(i)=1$ for all $i\perp pq$ then choose values of $p,q$ so \[0=\sum_{i=1}^n if(i) = \sum_{1\le i \le n, i\perp pq}i + pf(p)+xqf(q)\]by Bézout (where $x\in \{3,6\} = \{1+2,1+2+3\}$). Thus, it suffices to deal with the cases $n\le 15$. We then bash. For $n=3$, take $(f(1),f(2),f(3)) = (1,1,-1)$. For $n=4$, take $(f(1),f(2),f(3),f(4)) = (1,-1,-1,1)$. For $n=5$, take $(f(1),f(2),f(3),f(4),f(5)) = (1,1,1,1,-2)$. For $n=6$, take $(f(1),f(2),f(3),f(4),f(5),f(6)) = (1,-1,1,1,0,1)$. For $n=7$, we can use a similar Bézout argument with $p=7,q=5$ to generate a solution. For $8\le n \le 10$, take $(p,q)=(7,5)$ to generate a solution with Bézout. For $11\le n\le 15$, take $(p,q) = (11,7)$ to generate a solution with Bézout.
24.08.2020 02:54
The answer is all $n>2.$ $\textbf{Claim: }$ $n=2$ doesn't work. $\emph{Proof: }$ Suppose there exists an infinite sequence of nonzero integers $a_1,a_2,\dots$ such that $$a_1+2a_2=0,$$$$a_2+2a_4=0,$$$$a_3+3a_6=0,$$$$\vdots$$This implies that $a_1=(-2)^{i}a_{2^i}$ for all $i,$ which is impossible as $a_1\ne 0.$ $\blacksquare$ $\textbf{Claim: }$ $n=6,7,8,10,11,12,13,14,15$ and all $n\ge 16$ work. $\emph{Proof: }$ Let $p_1,p_2,\dots,p_m$ be the set of primes less than or equal to $n.$ Note that for all values of $n$ specified in the claim, there exists a prime in the interval $\left(\sqrt{n},\frac{n}{2}\right]$ (check manually for $n=6,7,8,10,11,12,13,14,15$ and choose a prime between $n/2$ and $n/4$ for $n\ge 16$). Let this prime be $p_a.$ By Bertrand's Postulate, there exists a prime (say $p_b$) between $\left\lceil\frac{n}{2}\right\rceil$ and $n.$ Let $x_{p_a}$ be a positive integer such that $x_{p_a}\equiv -\frac{1}{p_a}\pmod{p_b}$ and let $x_{p_i}=p_b$ if $i\ne a,b.$ We will deal with $x_{p_b}$ later. Consider the sequence defined by $$a_k=\prod_{i=1}^{m}x_{p_i}^{\nu_{p_i}(k)}.$$We have $$\frac{1}{a_k}(a_{k}+2a_{2k}+\dots + na_{nk}=\sum_{i=1}^{n}\left(i\prod_{p\mid i}x_p\right),$$where primes are counted with multiplicity. Observe that every term on the RHS except $p_{a}x_{p_a}$ and $1$ is divisible by $p_b.$ But $1+p_{a}x_{p_a}$ is divisible by $p_a,$ so the sum of the terms on the RHS is divisible by $p_b.$ Thus, there is some value of $x_{p_b}$ such that $p_{b}x_{p_b}$ is equal to negative the sum of the other terms on the RHS, which results in a sum of zero. $\blacksquare$ $\textbf{Claim: }$ $n=3,4,5,9$ work. $\emph{Proof: }$ For $n=3,$ take the sequence $a_k=(-2)^{\nu_2(k)}.$ For $n=4,$ take the sequence $a_k=(-1)^{\nu_2(k)+\nu_3(k)}.$ For $n=5,$ take the sequence $(-4)^{\nu_3(k)}.$ For $n=9,$ take the sequence $(-8)^{\nu_5(k)}.$ $\blacksquare$
13.03.2022 21:46
The answer is $n>2$. $n=1$ doesn't work because $a_1$ must equal $0$. $n=2$ doesn't work because $a_1+2a_2=0$, so $v_2(a_2)=v_2(a_1)-1$, and similarly $v_2(a_{2^k})=v_2(a_1)-k$, so for large enough $k$, $v_2(a_{2^k})<0$. Let $p,q$ be the two largest primes below $n$. $p>\frac{n}{2}$ by Bertrand's postulate, and $q>\frac{n}{4}$ by another application of Bertrand's postulate. Thus for $n\ge 16$, $q>\sqrt{n}$. For $n=3,5\le n\le 15$, we can verify that $q>\sqrt{n}$. Thus for $n=3,n>5$, we can construct $a$ in the following way: $a_1=1$ $a_{\text{primes less than q}}=p$ $a_{\text{primes greater than q}}=1$ (it doesn't matter what their values are) $a_q=c$ such that $qc\equiv -1\mod p$, which is possible by Bezout $a_p=\frac{-1}{p}(a_1+2a_2+\cdots (p-1)a_{p-1}+(p+1)a_{p+1}+\cdots na_n)$ $a_{c_1c_2}=a_{c_1}a_{c_2}$ for any $c_1,c_2$ (the sequence is multiplicative) Because the sequence is multiplicative, we only have to verify that $a_1+2a_2+\dots na_n=0$. It suffices to show that $a_1+2a_2+\cdots (p-1)a_{p-1}+(p+1)a_{p+1}+\cdots na_n\equiv 0\mod p$. Because every prime less than $q$ has output of $p$, and $q^2>n$, it suffices to show that $a_1+qa_q\equiv 0\mod p$, but this is true by construction. Now the only case left is $n=4$, but the following works in that case. $a_1=1$ $a_{2}=a_3=-1$ $a_{\text{primes greater than q}}=1$ (again it doesn't matter what their values are) $a_{c_1c_2}=a_{c_1}a_{c_2}$ for any $c_1,c_2$ (the sequence is also multiplicative)
31.08.2023 03:42
The answer is $n \neq 2$. Clearly $n=2$ fails, since by induction we should have $a_1=(-2)^ka_{2^k}$ for all $k$, which is absurd unless $a_1=0$. Now we provide a construction for the other $n$. First, impose the condition that $(a_i)$ is a completely multiplicative sequence, so it suffices to construct $a_1,\ldots,a_n$ (satisfying this multiplicativity condition) such that $a_1+2a_2+\cdots+na_n=0$. For $n=3$ take $(a_1,a_2,a_3)=(1,1,-1)$, and for $n=4$ take $(a_1,a_2,a_3,a_4)=(1,2,-7,4)$. Now assume $n \geq 5$; in this case I claim that there exist two primes $(p,q)$ with $n \geq p>n/2$ and $p>q>\sqrt{n}$. Indeed, If $5 \leq n \leq 6$ then take $(p,q)=(5,3)$. If $7 \leq n \leq 12$ then take $(p,q)=(7,5)$. If $n \geq 13$, then by Bertrand pick $p$ to be a prime in $(n/2,n)$ and $q$ to be a prime in $(n/4,n/2)$, which works since $\lceil n/4\rceil>\sqrt{n}$. Let $e=\lfloor n/q\rfloor<\sqrt{n}$. For $1 \leq i \leq n$, if $i \perp pq$ then set $a_i=1$. Then since $q^2>n$, for any $1 \leq i \leq e$ we have $a_{eq}=a_q$, and $$\sum_{i=1}^e eqa_{eq}=\frac{qe(e+1)a_q}{2}.$$Since we clearly have $e<p-1$, it follows that $\tfrac{qe(e+1)}{2} \perp p$, hence as $a_q$ varies the above expression can obtain any value modulo $p$; in particular, we should be able to pick $a_q$ such that $$p \mid \sum_{\substack{1 \leq i \leq n\\i \neq p}} ia_i,$$and we are then free to set $a_p$ to the correct value to make $a_1+2a_2+\cdots+na_n=0$. $\blacksquare$
05.01.2024 04:10
The answer is all $n \geq 3$. $n=2$ fails because the condition implies $a_i$ is even for every $i$, creating an infinite descent. For construction, let $\{a_i\}$ be a completely multiplicative sequence. In other words, we fix $a_1 = 1$ and $a_{ij}= a_i \cdot a_j$ for all $(i, j)$. Such a construction is obviously impossible by, say, expressing $n$ as a product of its prime factors. Then, it suffices to have $$a_k+2a_{2k}+\cdots+na_{nk} = a_k(a_1+2a_2+\cdots+na_n) = 0,$$which means we need only solve the $k=1$ case. Furthermore, for some $n = p_1^{k_1} p_2^{k_2} \cdots p_\ell^{k_\ell}$, we have $$a_1+2a_2+\cdots+na_n = \prod_{i=1}^\ell (a_1+2a_2+\cdots+p_ia_{p_i})^{k_i}$$so it suffices to show that we may force $a_1+2a_2+\cdots+p_ia_{p_i} = 0$ for any $p_i \mid n$. This is done for all $p_i \geq 3$ by fixing a prime $\frac{p_i}2 < q < p_i$ using Bertrand: we may pick all terms except for $a_q$ arbitrarily and then $a_q$ such that $a_1+2a_2+\cdots+(p_i-1)a_{p_i-1}$ is a multiple of $p_i$ as $\gcd(p, q) = 1$. This finishes the problem for all $n$ that isn't a power of two. If $n$ is a power of two, we cannot have $a_1 = 1$ and $a_1+2a_2 = 0$, so we instead force $a_1+2a_2+3a_3+4a_4 = 0$ by picking $a_2 \equiv -1 \pmod 3$ (yielding $a_1+2a_2+4a_4 \equiv 1-2+4 = 0 \pmod 3$) and then $a_3$ to satisfy the condition. This finishes the problem.
09.03.2024 21:42
Notice that $n = 2$ fails since then \[a_1 = -2a_2 = 4a_4 = -8a_8 = \cdots\]Now we'll construct as sequence for all $n \ge 3$. Let the sequence be multiplicative, so $a_{ij} = a_ia_j$ for any $i,j \ge 1$. Thus it suffices to find $a_1,\ldots,a_n$ such that \[\sum_{i = 1}^n i \cdot a_i =0\]First assume that $n \ge 25$. A stronger version of Betrand's postulate implies there exists primes $p$ and $q$ such that \[\frac{5}{6}n < p < n \text{ and } \frac{5}{6}p < q < p \implies \frac{n}{2}<\frac{25}{36}n < q < p <n\]Thus, let all $a_i = 1$ for all $i \le n$ such that $i \neq p,q$. Since both $p,q > \frac{n}{2}$, after we do this, the sequence is still multiplicative. Now we need to find $a_p$ and $a_q$ with \[pa_p+qa_q = \text{some constant}\]Since $\gcd(p,q) = 1$, such $a_p$ and $a_q$ exist by Bezout's Lemma. For $n<25$, do the following: If $17 \le n < 25$, then take $p = 17$ and $q = 13$ and repeat the argument above. If $13 \le n < 17$, then take $p = 13$ and $q = 11$ and repeat the argument above. If $11 \le n < 13$, then take $p = 11$ and $q = 7$ and repeat the argument above. For $n = 10$, take $(1,-1,-1,1,7,1,4,-1,1,-7)$ as the first $10$ numbers. For $7 \le n \le 9$, then take $p = 7$ and $q = 5$ and repeat the argument above. For $n = 6$, take $(1,-1,6,1,3,-6)$ as the first $6$ numbers. For $n = 5$, take $(1,-1,4,1,-3)$ as the first $5$ numbers. For $n = 4$, take $(1,-1,-1,1)$ as the first $4$ numbers. For $n = 3$, take $(1,1,-1)$ as the first $3$ numbers.
07.05.2024 01:50
Similar two primes solution as above except without Bezout (I wrote this up at school today had to use Word)
Attachments:

06.06.2024 20:55
We claim that the answer is always positive except for $n=2$. First of all, it's clear that no such sequence exists for $n=2$ since $v_2(a_1)$ would need to be arbitrarly large, which is impossible for any non zero $a_1$. Next, we exhibit sequences that work for $n=3,4,\ldots,8$ : $\star$ For $n=p$ prime, take $a_k=\left(-\frac{p-1}{2}\right)^{v_p(k)}$. $\star$ For $n=4$, take $a_k=(-1)^{v_2(k)+v_3(k)}$, and for $n=8$ take $a_k=(-1)^{v_2(k)+v_3(k)+v_5(k)}$. $\star$ For $n=6$, take $a_k=(-3)^{v_3(k)}\times 4^{v_5(k)}$. Here is what we do for a general $n$. We want to construct a sequence of the form $a_k=\prod_{p}A_p^{v_p(k)}$, where the product ranges over all primes $p\le n$ (all $A_p$'s are constant). Then, for such a sequence to work, the $A_p's$ must be the root of some multivariable polynomial. For $n=9$, take $A_2=A_3=1$, then, since the only $5$ and $7$ terms that show up will be $5A_5+7A_7$, we can adjust by Bezout to get a working sequence. For $n\ge 10$, take a prime $n/2<q\le n$ and a prime $r$ with $n/4<r\le n/2$. We assign the value $1$ to all $A_p$'s with $p\ne q,r$. Then, the monomials containing $r$'s will be either $rA_r$, or $rA_r+2rA_r=3rA_r$, or $rA_r+2rA_r+3rA_r=6rA_r$. On the other hand, the only monomial containing $q$ will be $qA_q$. Since $q>n/2$, we have $q\ge 7$, so again we get two coprime bases and the result follows with Bezout. $\square$
01.07.2024 14:21
We claim that \[\boxed{\text{$n$ works iff $n \geq 3$}}\]. It is obvious to see why $n=2$, does not work because of $\nu_2$ issues. We will prove the converse now. Lemma(Chebyshev's Estimate)There exists two distinct prime number in the range $\left(\frac{n}2,n\right]$ iff $n \neq 4$, $6$, $10$. Proof: Use the Prime Number Theorem and some manual computation. $\square$. So we will first prove the result holds for $n=4$, $6$, $10$. See that one can take $\bullet$ For $n=4$, take $a_k={(-1)}^{\nu_2(k)+\nu_3(k)}$. $\bullet$ For $n=6$, take $a_k={(-2)}^{\nu_2(k)} \cdot 2^{\nu_3(k)}$. $\bullet$ For $n=10$, take $a_k=2^{\nu_5(k)} \cdot {(-9)}^{\nu_7(k)}$. Now for the other $n$, let $\frac{n}2 <p \leq q \leq n$ and then look at the equation \[p(X-1)+q(Y-1)=-\frac{(n)(n+1)}2\]which obviously has solutions and see that \[a_k=X^{\nu_p(k)} \cdot Y^{\nu_q(k)} \text{ if $p \neq q$}\]\[a_k={(X+Y)}^{\nu_p(k)} \text{ if $p=q$}\]works fine.