Ukrajina 2008

Let one of the progressions $\{a_n\}$ which has the required maximal number $M$ of common members have the first member $a_0$ and denominator $q_0>1$. The progression has some common elements with set $A$. Let $n$ be the least number in $A$, which can also be found in the progression. Then you can define a new progression with the first member $b_0=n$ and the same denominator $q_0$. It has as many members in the set $A$ as progression $\{a_n\}$ and therefore we can take it as an initial one. Let $m$ be the next common member of the set $A$ that also belongs to the progression, i.e. in a new progression $b_0=n$, $b_k=b_0{q}_0^k=n{q}_0^k=m\Rightarrow q_0^k=\frac{m}{n}=\frac{u}{v}\in \mathbb{Q}$ where $\frac{u}{v}$ is an irreducible fraction and $n\le \frac{u}{v}=m$.

Let's show that $q_0^i\notin \mathbb{Q}$ if $1\le i<k$. By contradiction, let $q_0^i=\frac{s}{t}$, which is also an irreducible fraction. In this case $\left(\frac{u}{v}\right)=q_0^{ki}={\left(\frac{s}{t}\right)}^k$. Then $u^i{t}^k=s^k{v}^i$. This implies that $u^i=s^k$ and $v^i=t^k$, since $(u,v)=1\Rightarrow t^k\nmid v^i$ and vice versa $v^i\nmid t^k$. As $i<k$, $v>t$, and $b_0=n\nmid v\Rightarrow b_0=n\nmid t$. Therefore $b_i=b_0{q}_0^i=n\frac{s}{t}\in \mathbb{N}$, which contradicts the following condition: the first natural number after $n$ will be $b_k=b_0{q}_0^k=n\frac{u}{v}=m$.

It follows that the rational members of the chosen geometric progression may only be members of such a set as $b_0,b_0{q}_0^k,b_0{q}_0^{2k},\dots$. Therefore we can choose $q=q_0^k\in \mathbb{Q}$ and consider the progression $(b_0,q)$ with the first integer member $b_0=n$ and rational denominator $q$ where $q=\frac{p}{r}$ is an irreducible fraction.

The progression $(1,2)$ obviously has the maximum members in $A$ among all the progressions with integer denominators. They share 11 common elements. All these elements are powers of two: $1,2,4,\dots ,1024$. Let there be a progression with a rational exponent, which has more elements in $A$. Let it be progression $(n,\frac{p}{r})$. Thus, if $c_k=n{\left(\frac{p}{r}\right)}^k$ is an integer, i.e. $n:r^k$, all the preceding values of $c_i$ are integers too, $i=0,k$. Therefore, if the progression has at least 12 elements in $A$, then $c_{12}=n{\left(\frac{p}{r}\right)}^{11}$ should be an integer, which implies that $n:r^{11}$. As $\frac{p}{r}\notin \mathbb{N}$, $r\ge 2$. Therefore, $r^{11}\ge 2048$ and $n\ge 2048$. We've finished proving the given condition (An increasing geometric progression cannot have more than 11 members in the set $A$).