, 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$).