1. Zadatak

Tvrdnju zadatka dokazujemo indukcijom po $k$.

Za $k=0$ treba među brojevima $\{1,2,3,4,5\}$ odabrati 4 broja tako da među njima ne postoje tri uzastopna člana aritmetičkog niza. Jedini takav izbor je $\{1,2,4,5\}$.

Pretpostavimo da smo za neki $k\ge0$ izabrali skup $S_k$ koji sadrži $4\cdot2^k$ prirodnih brojeva koji nisu veći od $5\cdot3^k$ tako da se među brojevima tog skupa ne pojavljuju tri uzastopna člana aritmetičkog niza.

Označimo skup $T_k=\{10\cdot3^k+s:s\in S_k\}$. Skupovi $S_k$ i $T_k$ imaju isti broj elemenata. Tvrdimo da tada skup $S_{k+1}=S_k\cup T_k$ zadovoljava uvjete zadatka za $k+1$.

Skup $S_{k+1}$ ima $2\cdot(4\cdot2^k)=4\cdot2^{k+1}$ elemenata, i nijedan od njih nije veći od $10\cdot3^k+5\cdot3^k=5\cdot3^{k+1}$.

Uzmemo li bilo koja tri broja $a,b,c\in S_{k+1}$ takva da je $a<b<c$, vrijedi točno jedna od sljedećih mogućnosti:

1. $a,b,c\in S_k$
2. $a,b\in S_k$, $c\in T_k$
3. $a\in S_k$, $b,c\in T_k$
4. $a,b,c\in T_k$.

Želimo pokazati da je uvijek $a+c\ne2b$ iz čega slijedi tvrdnja zadatka za $k+1$, pa bi dokaz indukcijom time bio završen.

U 1. slučaju je $a+c\ne2b$ zbog pretpostavke da skup $S_k$ zadovoljava tvrdnju zadatka.

U 2. slučaju je $a+c\ge1+(10\cdot3^k+1)>10\cdot3^k\ge2b$, a u 3. slučaju je $a+c\le5\cdot3^k+5\cdot3^{k+1}=20\cdot3^k<2b$.

U 4. slučaju brojevi $a-10\cdot3^k$, $b-10\cdot3^k$, $c-10\cdot3^k$ pripadaju skupu $S_k$. Zato vrijedi

$$(a-10\cdot3^k)+(c-10\cdot3^k)\ne2(b-10\cdot3^k),$$

pa je i $a+c\ne2b$.

Time su svi slučajevi pokriveni i zadatak je riješen.