Track / Stage 6 / 219 of 400 #1699 of 2444

Problem 1699

National Olympiad, first round

Algebra Difficulty 6.4 Prove it Shortlist JBMO · JBMO · 2008

Consider an integer $n \geq 4$ and a sequence of real numbers $x_{1}, x_{2}, x_{3}, \ldots, x_{n}$ . An operation consists in eliminating all numbers not having the rank of the form $4k+3$ , thus leaving only the numbers $x_{3}, x_{7}, x_{11}, \ldots$ (for example, the sequence $4,5,9,3,6,6,1,8$ produces the sequence $9,1$ ). Upon the sequence $1,2,3, \ldots, 1024$ the operation is performed successively for 5 times. Show that at the end only one number remains and find this number.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Solution:
After the first operation 256 numbers remain; after the second one, 64 are left, then 16, next 4 and ultimately only one number.

Notice that the 256 numbers left after the first operation are $3,7, \ldots, 1023$ , hence they are in arithmetical progression of common difference 4. Successively, the 64 numbers left after the second operation are in arithmetical progression of ratio 16 and so on.

Let $a_{1}, a_{2}, a_{3}, a_{4}, a_{5}$ be the first term in the 5 sequences obtained after each of the 5 operations. Thus $a_{1}=3$ and $a_{5}$ is the requested number. The sequence before the fifth operation has 4 numbers, namely
$a_{4},\ a_{4}+256,\ a_{4}+512,\ a_{4}+768$
and $a_{5}=a_{4}+512$ . Similarly, $a_{4}=a_{3}+128$ , $a_{3}=a_{2}+32$ , $a_{2}=a_{1}+8$ .

Summing up yields $a_{5}=a_{1}+8+32+128+512=3+680=683$ .

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.