5. Zadatak

Ako broj $n$ nije među odabranima, onda je, prema Dirichletovom principu, među odabranim brojevima barem jedan od parova (kojih ima $n-1$)

$$\{i,2n-i\},\qquad i=1,2,\ldots,n-1.$$

No, zbroj brojeva u istom paru je $2n$ pa smo time gotovi.

Ako broj $n$ jest među odabranima, neka su $a_1,a_2,\ldots,a_{n-1}$ odabrani brojevi različiti od $n$. Pokažimo da među njima postoji njih nekoliko čiji je zbroj djeljiv s $n$.

Odabranih $n-1$ brojeva su brojevi iz skupa $\{1,\ldots,n-1,n+1,\ldots,2n-1\}$; primijetimo da se među njima svaki ostatak pri dijeljenju s $n$ (osim $0$) pojavljuje točno 2 puta. Kako je $n-1\ge3$, možemo pretpostaviti da brojevi $a_1$ i $a_2$ ne daju isti ostatak pri dijeljenju s $n$. Promotrimo niz

$$a_1,\quad a_2,\quad a_1+a_2,\quad\ldots,\quad a_1+a_2+\cdots+a_{n-1}.$$

Ako je neki od tih brojeva djeljiv s $n$, naša tvrdnja je dokazana, a ako nije, onda, po Dirichletovom principu, neka dva daju isti ostatak pri dijeljenju s $n$. Razlika ta dva broja je djeljiva s $n$, a ona je ili oblika $a_2-a_1$ (što se kosi s pretpostavkom da ta dva daju različit ostatak pri dijeljenju s $n$) ili oblika $a_i+a_{i+1}+\cdots+a_j$, pa tvrdnja opet vrijedi.

Konačno, znamo da među odabranim brojevima različitim od $n$ postoji njih nekoliko čiji je zbroj djeljiv s $n$. Taj zbroj je oblika $k\cdot n$; ako je $k$ paran, onda smo našli nekoliko brojeva čiji je zbroj djeljiv s $2n$, a ako je neparan, onda tim brojevima dodajmo još $n$ pa je takav zbroj oblika $(k+1)n$, što je djeljivo s $2n$.