3. Zadatak

Prvo rješenje.

Uočimo da je broj $\frac12n(n-1)$ nužno djeljiv s $3$, kako bi se štapovi mogli podijeliti u grupe po tri štapa. Dakle, $n$ nužno daje ostatak $0$ ili $1$ pri dijeljenju s $3$.

Pokažimo da je za takve $n$-ove to uvijek moguće postići.

Za $n=4$ možemo podijeliti štapove u dvije grupe koje se sastoje od dvije stranice kvadrata i jedne dijagonale te je od njih očito moguće sastaviti dva sukladna jednakokračna pravokutna trokuta. Nadalje, pretpostavimo da je $n\geq6$ broj koji daje ostatak $0$ ili $1$ pri dijeljenju s $3$.

Neka su $a_1<a_2<\ldots<a_k$ sve duljine štapova na raspolaganju. Sve duljine, osim možda zadnje, javljaju se točno $n$ puta u pravilnom $n$-terokutu, dok se duljina $a_k$ najveće dijagonale pojavljuje $\frac n2$ puta (ako je $n$ paran) ili $n$ puta (ako je $n$ neparan).

Uočimo da za pozitivne realne brojeve $a$ i $b$ takve da je $a>b$ možemo sastaviti jednakokračni trokut sa stranicama duljine $a,a$ i $b$. Zaista, očito vrijede nejednakosti

$$a+a>b\qquad\text{i}\qquad a+b>b.$$

Podjelu na grupe vršimo počevši s najvećim duljinama $a_k$. Ako štapova duljina $a_k$ imamo parno mnogo, tada ih sve rasporedimo u grupe koje se sastoje od duljina $a_k,a_k$ i $a_{k-1}$. Budući da je $a_k>a_{k-1}$, od takvih duljina moguće je sastaviti trokut. S druge strane, ako štapova duljina $a_k$ ima neparno mnogo, tada napravimo jednu grupu koja se sastoji od tri duljine $a_k$, a ostale rasporedimo u grupe koje se sastoje od duljina $a_k,a_k$ i $a_{k-1}$.

Kako je broj štapova duljina $a_k$ barem $\frac n2\geq3$, gornju podjelu u grupe uvijek možemo provesti, neovisno o parnosti tog broja.

Nakon ovog koraka preostali će broj duljina $a_{k-1}$ ponovo biti barem $\frac n2\geq3$ jer su u gornjoj podjeli one sudjelovale u najviše $\frac n2$ tročlanih grupa štapova (na početku ih je bilo $n$). Zato prethodni korak sada možemo ponoviti za preostale duljine $a_{k-1}$, pa nakon toga za duljine $a_{k-2}$ i tako sve do duljine $a_2$.

Nakon svih tih koraka su nam preostale samo još neke od duljina $a_1$ koje trebamo podijeliti u tročlane grupe. Broj duljina $a_1$ koji nam je preostao nužno je djeljiv s $3$ jer je broj svih štapova na početku bio djeljiv s $3$. Zato sve preostale duljine $a_1$ možemo podijeliti u tročlane grupe.

Time smo sve štapove podijelili u grupe od po tri štapa s kojima je moguće napraviti trokut, te su zaista takvi brojevi svi prirodni brojevi $n>3$ koji pri dijeljenju s $3$ daju ostatak $0$ ili $1$.

Drugo rješenje.

Kao u prošlom rješenju, zaključujemo da je $n$ nužno oblika $3m$ ili $3m+1$ za neki $m\in\mathbb N$, te da imamo po $n$ duljina štapova $a_1<\ldots<a_k$ na raspolaganju, osim možda $a_k=\frac n2$ u slučaju parnog broja $n$.

Ako je $n$ djeljiv s $3$, svi brojevi $a_1,\ldots,a_k$ djeljivi su s $3$, pa od svih štapova možemo napraviti jednakostranične trokute. Zato pretpostavljamo da je $n$ oblika $3m+1$.

U pravilnom mnogokutu $A_1A_2\ldots A_n$ primjećujemo da su za svaki $i\in\{1,\ldots,k\}$ duljine stranica trokuta $A_1A_2A_{i+2}$ jednake $a_1,a_i,a_{i+1}$. Posebno, za te duljine vrijede nejednakosti trokuta. Zato za sve takve indekse $i\geq2$ vrijedi i

$$a_{i-1}+a_i\geq a_1+a_i>a_{i+1},$$

pa zaključujemo da i od štapova duljina $a_{i-1},a_i$ i $a_{i+1}$ možemo sastaviti trokut.

Ako je $n$ neparan broj oblika $3m+1$, tada je broj $k$ (broj različitih duljina štapova) nužno djeljiv s $3$ (budući da je broj svih duljina štapova djeljiv s $3$). Za svaku od tih duljina na raspolaganju imamo $n=3m+1$ štapova. U tom slučaju ćemo napraviti po jednu grupu štapova duljina $a_{3i+1},a_{3i+2}$ i $a_{3i+3}$ ($0\leq i<\frac k3$). Nakon toga nam je preostalo $3m$ štapova svake duljine, pa kao u prethodnom slučaju od svih štapova stvorimo jednakostranične trokute.

Neka je na kraju $n$ paran broj oblika $3m+1$, odnosno $n=6l+4$, za neki $l\in\mathbb N_0$. Posebno, broj štapova duljina $a_{k-1}$ je $n=6l+4$ i daje ostatak $1$ pri dijeljenju s $3$, dok broj štapova $a_k$ daje ostatak $2$ pri dijeljenju s $3$. Zato je ukupan broj štapova duljina $a_k$ ili $a_{k-1}$ djeljiv s $3$, ali i broj svih preostalih štapova (čije su duljine manje ili jednake $a_{k-2}$) djeljiv s $3$. Slično kao u slučaju neparnog broja $n$ oblika $3m+1$, zaključujemo da je broj $k-2$ djeljiv s $3$, pa štapove duljina manjeg ili jednakog $a_{k-2}$ podijelimo kao u prošlom slučaju (prvo grupe štapova duljina $a_{3i+1},a_{3i+2}$ i $a_{3i+3}$, a zatim na jednakostranične trokute). Za duljine $a_k$ i $a_{k-1}$ prvo napravimo jedan trokut duljina $a_k,a_k$ i $a_{k-1}$ (da je to moguće argumentiramo slično kao ranije), a onda od svih ostalih štapova napravimo jednakostranične trokute, budući da je preostalo $3m$ štapova duljina $a_{k-1}$ i $6m$ štapova duljina $a_k$.

Ovime smo pokrili sve slučajeve, te su zaista takvi brojevi svi prirodni brojevi $n>3$ koji pri dijeljenju s $3$ daju ostatak $0$ ili $1$.