5. Zadatak

Najveća moguća vrijednost broja $n$ je $200$.

Pretpostavimo da postoji natjecatelj, nazovimo ga $X$, koji poznaje $201$ ostalih natjecatelja i neka tih $201$ natjecatelja tvori skup $S$. Dakle, moraju postojati i natjecatelji koji poznaju točno $1,2,\ldots,200$ ostalih natjecatelja.

Kažemo da natjecatelj ima stupanj $m$ ako poznaje točno $m$ drugih natjecatelja. Svaki natjecatelj iz skupa $S$ ima stupanj najviše $99$. Naime, ne smije poznavati nikoga iz $S$ jer ne postoje tri natjecatelja koji se svi međusobno poznaju, a osim $X$ i natjecatelja iz $S$ postoji još samo $98$ natjecatelja. Zaključujemo zapravo da natjecatelji iz $S$ imaju najviše $99$ različitih stupnjeva.

Istovremeno, natjecatelja koji nisu u skupu $S$ i koji nisu $X$ ima $98$, pa oni imaju najviše $98$ različitih stupnjeva. Time smo pokazali da natjecatelji imaju najviše

$$1+99+98=198<201$$

različitih stupnjeva, pa je nemoguće da postoje natjecatelji koji poznaju točno $1,2,\ldots,201$ ostalih natjecatelja. Dakle, ne postoji natjecatelj koji poznaje točno $201$ ostalih natjecatelja.

Pokažimo sada da je moguće da je $n=200$. Označimo $100$ natjecatelja s $A_1,A_2,\ldots,A_{100}$ i zovimo ih $A$-natjecateljima, a preostalih $200$ s $B_1,B_2,\ldots,B_{200}$ te ih zovimo $B$-natjecateljima.

Za svaki $i\in\{1,2,\ldots,100\}$ i svaki $j\in\{1,2,\ldots,200\}$ takve da je $i\le j$, neka se poznaju natjecatelji $A_i$ i $B_j$. Svi ostali parovi natjecatelja neka se međusobno ne poznaju.

Tvrdimo da je za ovakav raspored poznanstava $n=200$ i da su ispunjeni svi uvjeti zadatka. Ne postoje tri natjecatelja koji se svi međusobno poznaju zato što se nikoja dva među $A$-natjecateljima ne poznaju i nikoja dva među $B$-natjecateljima se međusobno ne poznaju.

Nadalje, za $i\in\{1,2,\ldots,100\}$ natjecatelj $A_i$ poznaje natjecatelje $B_i,B_{i+1},\ldots,B_{200}$ i samo njih. Dakle, on ima točno $201-i$ poznanika, što znači da postoje natjecatelji koji poznaju točno $200,199,\ldots,101$ ostalih natjecatelja.

Slično, za $j\in\{1,2,\ldots,100\}$ natjecatelj $B_j$ poznaje natjecatelje $A_1,\ldots,A_{j-1},A_j$ i samo njih. Odnosno, on ima točno $j$ poznanika, što znači da postoje natjecatelji koji poznaju točno $1,2,\ldots,100$ ostalih natjecatelja.

Prema tome, najveća moguća vrijednost je $200$.