4. Zadatak

Prvo rješenje.

Označimo sa $S$ skup odabranih $k+2$ brojeva. Bez smanjenja općenitosti možemo pretpostaviti da je 1 u skupu $S$. Zaista, ako se broj 1 ne nalazi u skupu $S$, svim elementima iz $S$ možemo oduzeti vrijednost najmanjeg elementa skupa $S$ i dodati 1, pritom će razlika između svaka dva elementa ostati sačuvana.

Ako se u skupu $S$ nalazi barem jedan broj $b$ iz skupa $\{k+2,k+3,\ldots,2k\}$, onda za brojeve 1 i $b$ vrijedi tvrdnja zadatka.

Pretpostavimo zato da niti jedan od brojeva $k+2,k+3,\ldots,2k$ nije u $S$. Sve brojeve od 2 do $3k+1$ možemo podijeliti u $k$ parova $(2,2k+1),\ldots,(k+1,3k)$. Osim broja 1, u skupu $S$ nalazi se još $k+1$ brojeva, pa prema Dirichletovom principu postoji par koji sadrži dva broja iz $S$. Ta dva broja zadovoljavaju tvrdnju zadatka.

Drugo rješenje.

Zapišimo odabrane brojeve u uzlaznom poretku, neka su to $1\leq a_1<a_2<\ldots<a_{k+2}\leq3k$. Tada vrijedi $a_{k+2}-a_1>k$. Ako je $a_{k+2}-a_1<2k$, onda su $a_1$ i $a_{k+2}$ traženi brojevi. Stoga pretpostavimo da je $a_{k+2}-a_1\geq2k$.

Neka je $i$ najveći indeks takav da vrijedi $a_{k+2}-a_i\geq2k$.

Uočimo da vrijedi $a_{j+1}-a_j\leq2k-1$ za svaki indeks $j=1,2,\ldots,k+1$. U suprotnom, zbog $a_j\geq j$ i $a_{k+2}\geq a_{j+1}+(k+2-j-1)$ vrijedilo bi

$$a_{k+2}\geq a_{j+1}+(k+2-j-1)>a_j+2k-1+(k+2-j-1)\geq3k,$$

što je nemoguće.

Posebno, vrijedi $a_{k+2}-a_{k+1}\leq2k-1$, iz čega slijedi $i<k+1$.

Također, prema definiciji indeksa $i$ vrijedi $a_{k+2}-a_{i+1}<2k$. Ako je $a_{k+2}-a_{i+1}>k$, onda su $a_{k+2}$ i $a_{i+1}$ traženi brojevi.

Pretpostavimo zato da je $a_{k+2}-a_{i+1}\leq k$. U tom slučaju, zbog $a_{k+2}-a_i\geq2k$ slijedi $a_{i+1}-a_i\geq k$.

Ako je $a_{i+1}-a_i>k$. Tada, zbog $a_{i+1}-a_i\leq2k-1<2k$ vrijedi da su $a_{i+1}$ i $a_i$ traženi brojevi.

Ako je $a_{i+1}-a_i=k$, onda imamo

$$k\geq a_{k+2}-a_{i+1}=a_{k+2}-a_i-k\geq2k-k=k,$$

pa slijedi $a_{k+2}-a_{i+1}=k$.

Pretpostavimo da vrijedi $i<k$. Tada postoji $\ell$ takav da je $i+1<\ell<k+2$. Tada je $a_\ell-a_i>a_{i+1}-a_i=k$ i $a_\ell-a_i<a_{k+2}-a_i\leq2k$, pa su $a_i$ i $a_\ell$ traženi brojevi.

Ako vrijedi $i+1=k+1$, tada je $a_{k+2}-a_{k+1}=k$ i $a_{k+2}-a_k=2k$. Budući da je $a_k+2k=a_{k+2}\leq3k$, tj. $a_k\leq k$, a vrijedi i $a_k\geq k$, zaključujemo da je $a_k=k$. Sada je $1\leq a_1<a_2<\ldots<a_k=k$, pa mora biti $a_j=j$ za sve $j=1,2,\ldots,k$. Također, vrijedi $a_{k+1}=2k$ i $a_{k+2}=3k$. Sada su traženi brojevi, na primjer, $a_1$ i $a_{k+1}$.

U svim slučajevima smo pronašli traženi par brojeva, pa je time tvrdnja zadatka dokazana.