Kvant Math Problem 1029

Verified: no
Verdicts: PASS + FAIL
Solve time: 14m55s
Source on kvant.digital

Problem

Among $n$ terms of an arithmetic progression, it was possible to select $k$ terms forming an increasing geometric progression. Prove that $n\ge2^{k-1}$.

V. F. Lev

Solution

Let the arithmetic progression be

$$a,\ a+d,\ a+2d,\ \dots,\ a+(n-1)d,$$

with $d\neq 0$. Among its terms, suppose that $k$ of them form an increasing geometric progression

$$b_1<b_2<\cdots<b_k .$$

Let the common ratio of this geometric progression be $q>1$. Since each $b_i$ is a term of the arithmetic progression, there exist integers

$$0\le m_1<m_2<\cdots<m_k\le n-1$$

such that

$$b_i=a+m_i d.$$

Because all $b_i$ belong to the same arithmetic progression, every difference $b_j-b_i$ is an integer multiple of $d$. In particular,

$$b_{i+1}-b_i=(q-1)b_i$$

is divisible by $d$ for every $i$.

Write

$$x_i=\frac{b_i}{d}.$$

Then each $x_i$ is rational, and

$$(q-1)x_i\in\mathbb Z \qquad (i=1,\dots,k-1).$$

Since $b_{i+1}=qb_i$, we also have

$$x_{i+1}=q x_i.$$

Set

$$r=q-1.$$

Then $r x_i$ is an integer for every $i<k$. Let

$$y_i=r x_i.$$

The numbers $y_i$ are integers and satisfy

$$y_{i+1}=q y_i=(1+r)y_i.$$

Hence

$$y_{i+1}-y_i=r y_i.$$

Since $y_i$ and $y_{i+1}$ are integers, $r y_i$ is an integer. Let

$$r=\frac{u}{v}$$

in lowest terms. From $r y_i\in\mathbb Z$ it follows that $v\mid y_i$ for every $i<k$.

Now

$$y_{i+1}=\frac{u+v}{v},y_i.$$

Because $\gcd(u+v,v)=1$, divisibility by $v$ improves by at least one power at each step. More precisely, if $v^t\mid y_i$, then

$$v^{t+1}\mid y_{i+1}.$$

Starting with $y_1$, induction yields

$$v^{i-1}\mid y_i \qquad (i=1,\dots,k).$$

Since the geometric progression is increasing, $q>1$, hence $r>0$. Therefore $u\ge1$. If $v\ge2$, then

$$y_i\ge v^{,i-1}\ge 2^{,i-1}.$$

Consequently,

$$y_k-y_1 \ge 2^{k-1}-1.$$

Returning to the original arithmetic progression,

$$y_i=r x_i=\frac{q-1}{d},b_i =\frac{b_{i+1}-b_i}{d}.$$

Thus each $y_i$ equals the number of steps of the arithmetic progression between $b_i$ and $b_{i+1}$:

$$m_{i+1}-m_i=y_i.$$

Hence

$$m_k-m_1 =\sum_{i=1}^{k-1}(m_{i+1}-m_i) =\sum_{i=1}^{k-1} y_i.$$

Since the positive integers $y_i$ satisfy

$$y_i\ge 2^{i-1},$$

we obtain

$$m_k-m_1 \ge \sum_{i=1}^{k-1}2^{i-1} =2^{k-1}-1.$$

The indices $m_1,\dots,m_k$ all lie between $0$ and $n-1$, so

$$n-1\ge m_k-m_1.$$

Combining the inequalities gives

$$n-1\ge 2^{k-1}-1,$$

and therefore

$$n\ge 2^{k-1}.$$

This is exactly the required statement. ∎