3. Zadatak

Prvo rješenje

Od danih $4n$ točaka možemo na $\binom{4n}{3}$ načina odabrati tri točke. Međutim, te tri točke bit će vrhovi trokuta samo ako ne leže na istoj stranici. Prebrojimo na koliko načina možemo odabrati tri točke na jednoj stranici kvadrata. Kako je na svakoj stranici $n+1$ točka (uključujući i vrhove), to očito možemo na $\binom{n+1}{3}$ načina. Isto vrijedi za svaku od četiri stranice kvadrata pa ranije dobiveni broj treba umanjiti za $4\binom{n+1}{3}$. Konačno, traženi broj trokuta je

$$\boxed{\binom{4n}{3}-4\binom{n+1}{3}}.$$

Drugo rješenje

Razvrstajmo trokute prema tome koliko vrhova trokuta su ujedno i vrhovi kvadrata. Razlikujemo četiri slučaja.

1. Sva tri vrha trokuta su vrhovi kvadrata. Takvih trokuta ima $4$.

2. Dva vrha trokuta su vrhovi kvadrata. Imamo $4$ para vrhova koji leže na istoj stranici. Za treći vrh trokuta onda možemo odabrati bilo koju od preostalih $3n-3$ točaka koje ne leže na toj stranici. Imamo $2$ para nasuprotnih vrhova kvadrata. Za treći vrh trokuta možemo odabrati bilo koju od preostalih $4n-4$ točaka. Dakle, ukupno trokuta ovog tipa ima

$$4(3n-3)+2(4n-4)=20(n-1).$$

3. Točno jedan vrh trokuta je vrh kvadrata. Na $4$ načina možemo odabrati vrh kvadrata. Razlikujemo tri podslučaja:

   a) Oba preostala vrha se nalaze na stranicama uz istaknuti vrh. Takvih trokuta ima $(n-1)^2$.

   b) Oba preostala vrha nalaze se na stranicama nasuprot vrhu. Takvih trokuta ima $\binom{2n-2}{2}$.

   c) Jedan preostali vrh je uz istaknuti vrh kvadrata, a drugi nasuprot njemu. Na $2n-2$ načina biramo točku uz vrh, i na $2n-2$ načina biramo točku nasuprot vrhu. Takvih trokuta ima $(2n-2)^2$.

   Dakle, ukupno trokuta ovog tipa ima

   $$4\left((n-1)^2+\binom{2n-2}{2}+(2n-2)^2\right)=4(7n^2-15n+8).$$

4. Nijedan vrh trokuta nije vrh kvadrata. Ako su svi vrhovi na različitim stranama, takvih trokuta ima $4(n-1)^3$. Ako su $2$ vrha na istoj strani, takvih trokuta ima

$$4\binom{n-1}{2}(3n-3)=6(n-1)^2(n-2).$$

Dakle, ukupno trokuta ovog tipa ima $4(n-1)^3+6(n-1)^2(n-2)$.

Dakle, traženih trokuta ukupno ima

$$\begin{aligned} &4+20(n-1)+4(7n^2-15n+8)+4(n-1)^3+6(n-1)^2(n-2)\\ &\qquad=10n^3-8n^2+2n. \end{aligned}$$

Treće rješenje

Biramo redom tri vrha trokuta. Prvi odabrani vrh trokuta može biti vrh kvadrata ili neka od preostalih točaka.

1. slučaj

Prvi vrh možemo izabrati na $4n-4$ načina ako ne uzmemo jedan od vrhova kvadrata.

1.1. U tom slučaju, drugi vrh možemo odabrati na $3n-1$ načina ako ne želimo da bude na istoj stranici kao prvi vrh. Treći vrh tada može biti bilo koja od preostalih $4n-2$ točaka.

1.2. U slučaju da drugi vrh želimo na istoj stranici ($n$ načina), treći vrh ne smije biti na toj istoj stranici pa ga možemo izabrati na $3n-1$ načina.

Ukupno u 1. slučaju postoji

$$(4n-4)\left((3n-1)(4n-2)+n(3n-1)\right)$$

mogućnosti.

2. slučaj

Druga je mogućnost da prvi vrh biramo među vrhovima kvadrata ($4$ načina).

2.1. U tom slučaju, drugi vrh možemo izabrati na $2n$ načina tako da bude na istoj stranici kao i prvi vrh. U tom slučaju preostaje nam $3n-1$ mogućnosti za treći vrh.

2.2. Ukoliko drugi vrh nije na istoj stranici kao i prvi ($2n-1$ načina), treći vrh može biti bilo koja od preostalih $4n-2$ točaka.

Ukupno u 2. slučaju imamo

$$4\left(2n(3n-1)+(2n-1)(4n-2)\right)$$

mogućnosti.

Ovakvim brojanjem svaki od trokuta smo brojali $3!=6$ puta, jer poredak vrhova trokuta nije bitan, stoga ukupni broj traženih trokuta iznosi

$$\begin{aligned} \frac16\Big[&(4n-4)\left((3n-1)(4n-2)+n(3n-1)\right)\\ &+4\left(2n(3n-1)+(2n-1)(4n-2)\right)\Big] =10n^3-8n^2+2n. \end{aligned}$$