Magyar Information Contest Journal Articles

Problem A. 628. (November 2014)

A. 628. Is it true that for every infinite sequence $\displaystyle x_1,x_2,\ldots$ of integers satisfying $\displaystyle |x_{k+1}-x_k|=1$ for every positive integer $\displaystyle k$, there exists a sequence $\displaystyle k_1<k_2<\ldots<k_{2014}$ of positive integers such that as well the indices $\displaystyle k_1,k_2,\ldots,k_{2014}$ as the numbers $\displaystyle x_{k_1},x_{k_2},\ldots,x_{k_{2014}}$ (in this order) form arithmethic progressions?

Proposed by: E. Csóka, Warwick and Ben Green, Oxford

(5 pont)

Deadline expired on 10 December 2014.

Solution. The answer is NO. We provide a sequence whose neighboring terms have difference $\displaystyle \pm 1$, but for which there do not exist appropriate indices $\displaystyle k_1<\ldots<k_{2014}$.

Define

$\displaystyle f(t) = \sum_{n=1}^\infty 50^n \sin\frac{t}{100^n}$

(this series converges for all real $\displaystyle t$, because $\displaystyle \left|50^n \sin\frac{t}{100^n}\right|<\frac{|t|}{2^n}$), and for each positive integer $\displaystyle k$, let $\displaystyle x_k$ be an integer with the same parity as $\displaystyle k$ and $\displaystyle \big|x_k-f(k)\big|\le1$. We claim that this sequence works.

First, we verify that $\displaystyle |x_{k+1}-x_k|=1$. It is well-known that for any distinct reals $\displaystyle u,v$, $\displaystyle \big|\sin u-\sin v\big|<|u-v|$, hence

$\displaystyle \big|f(u)-f(v)\big| = \left| \sum_{n=1}^\infty 50^n \bigg(\sin\frac{u}{100^n}-\sin\frac{u}{100^n}\bigg)\right| \le \sum_{n=1}^\infty 50^n \left| \sin\frac{u}{100^n}-\sin\frac{u}{100^n}\right| <$

$\displaystyle < \sum_{n=1}^\infty 50^n \frac{|u-v|}{100^n} = |u-v| \sum_{n=1}^\infty \left(\frac12\right)^n = |u-v|.$

Applying this in the case $\displaystyle (u,v)=(k,k+1)$, we find

$\displaystyle |x_k-x_{k+1}| \le \big|x_k-f(k)\big| + \big|f(k)-f(k+1)\big| + \big|f(k+1)-x_{k+1}\big| < 1+1+1 = 3.$

But since $\displaystyle x_k-x_{k+1}$ is odd, we must have $\displaystyle |x_k-x_{k+1}|=1$.

Now consider an arithmetic progression $\displaystyle k_1<\ldots<k_{2014}$ with difference $\displaystyle d$. Note that $\displaystyle d$ lies between two neighboring powers of $\displaystyle 100$, so $\displaystyle 100^{m-1}\le d \le 100^m$ for some positive integer $\displaystyle m$. Define $\displaystyle h$ to be the largest positive integer with $\displaystyle hd\le 100^m$; then we have $\displaystyle h\le 100$, but

$\displaystyle \frac{100^m}2 < hd \le 100^m.$

Note that $\displaystyle \frac{k_{101}}{100^m}, \frac{k_{102}}{100^m}, \ldots, \frac{k_{800}}{100^m}$ form an arithmetic progression of difference at most $\displaystyle 1$ (and also that the first and last term have difference $\displaystyle >2\pi$), hence for some index $\displaystyle 101\le i\le 800$, the remainder of $\displaystyle \frac{k_i}{100^m}$ mod $\displaystyle 2\pi$ lies in the range $\displaystyle \left(\frac{\pi}{3};\frac{2\pi}{3}\right)$; for this index, $\displaystyle \sin\frac{k_i}{100^m}>\sin\frac\pi3$. Fix such an index $\displaystyle i$, and consider the quantity

$\displaystyle \Delta = (x_{k_i+hd} - x_{k_i}) - (x_{k_i} - x_{k_i-hd}) = x_{k_i+hd} - 2x_{k_i} + x_{k_i-hd}.$

If $\displaystyle x_{k_i-hd}, x_{k_i}, x_{k_i+hd}$ form an arithmetic progression, then $\displaystyle \Delta=0$. We will now proceed to show that $\displaystyle \Delta\neq 0$, obtaining a contradiction. For the sake of simplicity, use the notation $\displaystyle K=k_i$ and $\displaystyle D=hd$. Then $\displaystyle \frac12<\frac{D}{100^m}\le1$, $\displaystyle 1\le K-D < K < K+D \le 900$, and

$\displaystyle \Delta = x_{K+D} - 2x_K + x_{X-D}.$

Let's substitute in the definition of the sequence, write down $\displaystyle \Delta$ in terms of $\displaystyle f$, and bound from below using the $\displaystyle m$-th term:

$\displaystyle |\Delta| \ge \big| f(K+D) - 2f(K) + f(K-D) \big| - 4 = \left| \sum_{n=1}^\infty 50^n\bigg(\sin\frac{K+D}{100^n}-2\sin\frac{K}{100^n}+\sin\frac{K-D}{100^n}\bigg)\right| -4 \ge$

$\displaystyle \ge 50^m\bigg|\sin\frac{K+D}{100^m}-2\sin\frac{K}{100^m}+\sin\frac{K-D}{100^m}\bigg| -$

 $\displaystyle -\sum_{n=1}^{m-1} 50^n\bigg|\sin\frac{K+D}{100^n}-2\sin\frac{K}{100^n}+\sin\frac{K-D}{100^n}\bigg| -\sum_{n=m+1}^\infty 50^n\bigg|\sin\frac{K+D}{100^n}-2\sin\frac{K}{100^n}+\sin\frac{K-D}{100^n}\bigg| -4.$ $\displaystyle (1)$

Applying the identity

$\displaystyle \sin(a+b)-2\sin a +\sin(a-b) = \big(\sin(a+b)-\sin a\big)-\big(\sin a-\sin(a-b)\big) =$

 $\displaystyle = 2\sin\frac{b}2\bigg(\cos\frac{2a+b}2-\cos\frac{2a-b}2\bigg) = - 4 \sin^2\frac{b}2 \sin a$ $\displaystyle (2)$

provides the following lower estimate of the $\displaystyle m$-th term:

$\displaystyle 50^m\bigg|\sin\frac{K+D}{100^m}-2\sin\frac{K}{100^m}+\sin\frac{K-D}{100^m}\bigg| = 50^m \cdot 4\sin^2\frac{D}{2\cdot 100^m}\sin\frac{K}{100^m} >$

 $\displaystyle > 50^m \cdot 4\sin^2\frac14\cdot\sin\frac\pi3 > \frac{50^m}5.$ $\displaystyle (3)$

Moreover, using $\displaystyle (2)$ again, we have

$\displaystyle \sum_{n=m+1}^\infty 50^n\bigg|\sin\frac{K+D}{100^n}-2\sin\frac{K}{100^n}+\sin\frac{K-D}{100^n}\bigg| = \sum_{n=m+1}^\infty 50^n \cdot 4\sin^2\frac{D}{2\cdot 100^n}\left|\sin\frac{K}{100^n}\right| <$

 $\displaystyle < \sum_{n=m+1}^\infty 50^n \cdot 4\left(\frac{D}{2\cdot 100^n}\right)^2\cdot 1 < \sum_{n=m+1}^\infty 50^n \cdot 4\left(\frac{100^m}{2\cdot 100^n}\right)^2 = 50^m \sum_{\ell=1}^\infty \left(\frac1{200}\right)^\ell = \frac{50^m}{199} < \frac{50^m}{100}.$ $\displaystyle (4)$

Estimating the value of all the sines by $\displaystyle 1$ for small indices (i.e. when $\displaystyle n<m$), we find

$\displaystyle \sum_{n=1}^{m-1} 50^n\bigg|\sin\frac{K+D}{100^n}-2\sin\frac{K}{100^n}+\sin\frac{K-D}{100^n}\bigg| \le \sum_{n=1}^{m-1} 50^n \cdot 4 =$

 $\displaystyle = 50^m\cdot 4\sum_{\ell=1}^m \left(\frac1{50}\right)^\ell < 50^m\cdot 4\sum_{\ell=1}^\infty \left(\frac1{50}\right)^\ell = 50^m\cdot \frac4{49} < \frac{50^m}{10}.$ $\displaystyle (5)$

Finally, putting estimates $\displaystyle (3-5)$ into $\displaystyle (1)$, we obtain the contradiction

$\displaystyle |\Delta| > \frac{50^m}{5} - \frac{50^m}{100} - \frac{50^m}{10} - 4 = 50^m\cdot\frac{9}{100} - 4 > 0.$

Therefore, $\displaystyle x_{k_1},\ldots,x_{k_{2014}}$ can never form an arithmetic progression.

Statistics:

 2 students sent a solution. 0 point: 2 students.

 Our web pages are supported by: Morgan Stanley