5. Zadatak

Grupirajmo promatrane brojeve u skupove:

$$\begin{aligned} A_0&=\{1\},\\ A_1&=\{2,3\},\\ A_2&=\{4,5,6,7\},\\ A_3&=\{8,9,\ldots,15\},\\ A_4&=\{16,17,\ldots,31\},\\ A_5&=\{32,33,\ldots,63\},\\ A_6&=\{64,65,\ldots,127\},\\ A_7&=\{128,129,\ldots,255\}. \end{aligned}$$

U skupu $A_k$ nalazi se $2^k$ brojeva, za $k=0,\ldots,7$. Uočimo da se brojevi $n$ i $2n$ nalaze redom u $A_k$ i $A_{k+1}$ za neki $k$.

Neka su izvučeni svi brojevi iz skupova $A_1,A_3,A_5,A_7$. Tih brojeva ima $2+8+32+128=170$ i među njima nijedan nije dvostruko veći od nekog drugog.

Pokažimo da nije moguće odabrati više od 170 brojeva koji ispunjavaju uvjet. Neka je iz skupa $A_k$ izvučeno $a_k$ brojeva, za $k=0,\ldots,7$. Promotrimo skupove $A_k$ i $A_{k+1}$. Za svaki $m\in A_k$ broj $2m$ je u skupu $A_{k+1}$. Takvih parova $(m,2m)$ ima $2^k$. Očito je izvučen najviše jedan broj iz svakog para.

Osim tih brojeva, u skupu $A_{k+1}$ je još $2^k$ neparnih brojeva, pa je iz skupova $A_k$ i $A_{k+1}$ ukupno izvučeno najviše $2^k+2^k=2^{k+1}$ brojeva. To znači da je

$$a_0+a_1\le2^1,\quad a_2+a_3\le2^3,\quad a_4+a_5\le2^5,\quad a_6+a_7\le2^7.$$

Zbrajanjem tih nejednakosti dobivamo

$$a_0+a_1+\cdots+a_7\le170.$$

Time smo pokazali da je najveći mogući $N$ jednak 170.