Restate the problem as follows: Prove that in an arithimethical progression consisting of $ 40$ different positive integers, at least one among them can't be written in the form $ 2^k + 3^l.$ Where $ k,l$ are nonnegative integers.

This is official proof,I wish to see more proofs here

Attachments:

I think it is more like a number theory one than algebraic one

That is a kick *** solution. Nice work hxy09.

Thank you ahmedMido One of my friends from Shanghai told me it can be killed by $ mod 23$Can anybody continue with it?

Strange solution, it seems like 40 can be reduced, even for this proof. Congratulations hxy09, by the way. When will the Chinese team be announced? - it looks like you are in -

I heard that no one got this problem during the test. Is that true?

Quote: I heard that no one got this problem during the test. Is that true? Actually, quite to the contrary, a lot of people got this problem. It just takes a bit of time to realize that a combination of modular arithmetic and algebraic estimates work well together. Btw, the longest such arithmetic progression has 6 terms.

Seriously? Wow! Sorry, I just heard from some person that there was a question in the China TST 2009/2010 which no one got and was like algebra/number theory, so I just guessed it was this one.

From what I heard, this inequality had a very low score: http://www.artofproblemsolving.com/community/c6h265482p1440850 But I think the following is even more difficult (being taken directly from an Erdos paper): http://www.artofproblemsolving.com/community/c6h366317p2015072 In my year (2008), nobody solved this (Ljunggren result): http://www.artofproblemsolving.com/community/c6h198296p1090306 Actually that whole test had only 11 problems solved in total by about 40 contestants.

Wow, so difficult! Thanks!

hxy09 wrote: Thank you ahmedMido One of my friends from Shanghai told me it can be killed by $ mod 23$Can anybody continue with it? Really wonderful and fantastic solution! May I ask how you and your friends come up with such a cool solution?

A fact easy to be confirmed is that $ 2^m + 3^n$ will never be the multiple of $23$ ,which doesn't seem to do an effective work without algebra inequalities help to estimate.

"Actually, quite to the contrary, a lot of people got this problem. It just takes a bit of time to realize that a combination of modular arithmetic and algebraic estimates work well together. Btw, the longest such arithmetic progression has 6 terms." Here is a solution without any number theory or modular arithmetic whatsoever. Assume that such a progression existed. Look at the last $20$ terms, so they are all within a factor of $\frac{39}{20}=1.95$. Then for each term $2^m+3^n$, let $f(2^m+3^n)$ be whichever of $2^m, 3^n$ is bigger. Clearly Since $2f(x)>x>f(x)$, this means all values of $f$ on these last $20$ are within a factor of $3.9$. Since $f$ only takes on powers of $2$ and $3$, there exists $A$ and $B$ so that the range of $f$ on these last $20$ terms is contained in $\{2^A, 2^{A+1}, 3^B, 3^{B+1}\}$. Now, look at the subset of these last $20$ where $f(x)=2^M$ for some fixed $M$. If there are at least $5$ of them, then $2^M+3^{x_1}<2^M+3^{x_2}<2^M+3^{x_3}<2^M+3^{x_4}<2^M+3^{x_5}$ are in an arithmetic progression of length $20$, so $3^{x_5}-3^{x_1} \le 19(3^{x_2}-3^{x_1})$. This is impossible, as $\frac{3^{x_5}-3^{x_1}}{3^{x_2}-3^{x_1}} \ge \frac{27(3^{x_2})-3^{x_1}}{3^{x_2}-3^{x_1}} \ge 27$. Hence, $f$ hits each of $2^A, 2^{A+1}$ at most $4$ times among these last $20$. But similarly, if $f(x)=3^N$ for $7$ values $2^{x_i}+3^N$ for $1 \le i \le 7$, we get that $19 \ge \frac{2^{x_7}-2^{x_1}}{2^{x_2}-2^{x_1}} \ge 32$, a contradiction. So of these among last $20$, $f$ hits $2^A, 2^{A+1}$ $4$ times each and $3^B, 3^{B+1}$ $6$ times each. Among the last $20$ there are some $3^B+2^{a_i}$ for $1 \le i \le 6$, all at most $2(3^B)$, and then some $3^{B+1}+2^{b_i}$ for some $1 \le i \le 6$. So the latter $6$ must be among the last $14$, and then $2^{b_6}-2^{b_1} \le 13(2^{b_2}-2^{b_1})$, a contradiction.

There is an even more effortless solution to this problem. Look at the final $30$ terms of the AP, which are off by a factor of at most $\frac{39}{10}$. We let $f(2^m+3^n)=\max(2^m,3^n)$ again. Then on these terms, $f$ is off by a factor of at most $\frac{39}{5}<8$, so there exist $A,B$ so that the range of $f$ is contained in $2^A, 2^{A+1}, 2^{A+2}, 3^B, 3^{B+1}$. But there are at most $6$ points with $f=2^M$ and at most $5$ with $f=3^N$ by a similar argument as before. As $30>28$ we are done.

HuangZhen wrote: A fact easy to be confirmed is that $2^m + 3^n$ will never be the multiple of $23$ ,which doesn't seem to do an effective work without algebra inequalities help to estimate. Let me write down the complete mod $23$ solution here: first note that $p=23$ is the smallest prime mod which $2,3$ are quadratic residues while $-1$ is not ($\Leftrightarrow p\equiv-1$ mod $24$). The property guarantees $2^m + 3^n$ is never a multiple of $p$, therefore if at least $p$ such integers form an arithmetic progression they must be congruent to each other mod $p$. On the other hand for any prime $p\equiv-1$ mod $4$ and $k\in(\mathbb{Z}/p)^\times$, from the identity \[\sum_{x=0}^{p-1}\left(\frac{k-x^2}{p}\right)=1\]one can deduce the number of ways to write $k$ as an ordered sum of two nonzero quadratic residues are $\frac{p-1}{4}-\frac{1}{2}\left(\frac{k}{p}\right)$. Thus when $2^m + 3^n$ varies in any fixed residue class mod $23$, there are $\leq 6$ possibilities of $(2^m,3^n)$ mod $23\longleftrightarrow(m,n)$ mod $12$. Finally if $3$ different pairs of $(m,n)$ are congruent to each other mod $12$, then the ratio between the largest and smallest values of $2^m+3^n$ is greater than $2^{11}$ so these values surely don't fit into an arithmetic progression of positive integers with $\leq 40$ terms. Therefore an arithmetic progression with terms of the form $2^m+3^n$ and congruent to each other mod $23$ couldn't have $>12$ terms.

There does not even exist such a progression with $13$ terms. Suppose for the sake of contradiction that such a progression exists. Both $2$ and $3$ are quadratic residues modulo $23,$ and $-1$ is not. So $2^m + 3^n$ is never a multiple of $23,$ and all terms of the progression are congruent to a nonzero residue $\pmod{23}.$ Consider the set $S$ of ordered pairs $(j,k)$ of not-necessarily-distinct nonzero quadratic residues $\pmod{23}.$ It is known that there are $5$ nonzero quadratic residues $k$ such that $k+1$ is also a quadratic residue, and $6$ nonzero quadratic residues where $k+1$ is not a quadratic residue. For any arbitrary nonzero quadratic residue $j,$ we may multiply by $j$ each of the $5$ nonzero quadratic residues $k$ where $k+1$ is also a quadratic residue, yielding $5$ nonzero quadratic residues $j$ less than a quadratic residue. We may also multiply by $j$ each of the $6$ nonzero quadratic residues $k$ where $k+1$ is not a quadratic residue, yielding $6$ nonzero quadratic residues $j$ less than a quadratic nonresidue. So there are $5 \times 11= 55$ pairs in $S$ summing to a nonzero quadratic residue (two nonzero quadratic residues cannot sum to $0$) and $6 \times 11 = 66$ summing to a quadratic nonresidue. Given two nonzero quadratic residues $p$ and $q,$ we claim the number of pairs in $S$ summing to $p$ is the same as the number of pairs in $S$ summing to $q.$ This is because each pair of the former type can be multiplied by $\frac{q}{p}$ to get a pair of the latter type, and each pair of the latter type can be multiplied by $\frac{p}{q}$ to get a pair of the former type. So there are exactly $5$ pairs in $S$ summing to every nonzero quadratic residue. Similarly, there are exactly $6$ pairs in $S$ summing to every quadratic nonresidue. In our sequence of terms of the form $2^m + 3^n,$ there are at most $6$ possibilities for the remainders of $(m,n) \pmod{12}.$ By the Pigeonhole Principle, the remainders of $(m,n) \pmod{12}$ are constant across at least three terms. Either the largest of these terms is at least $2^{12}$ times the smallest, or we have three terms of the form $2^{m} + 3^{n}, 2^{m+12} + 3^{n}, 2^{m+24} + 3^{n},$ or $2^{m} + 3^{n}, 2^{m} + 3^{n+12}, 2^{m} + 3^{n+24}.$ Both possibilities are impossible in a progression of $13$ terms. $\square$