5. Zadatak

Dokazat ćemo da $N$ može poprimiti bilo koju vrijednost iz skupa

$$\{675,676,\ldots,1010,1011\}.$$

Iz uvjeta zadatka, obje osobe koje sjede uz osobu koja govori istinu nužno lažu. S druge strane, uz svaku osobu koja laže sjedi barem jedna osoba koja govori istinu.

Posebno, od dvije osobe koje sjede jedna pored druge barem jedna laže (inače bi te obje osobe imale susjeda koji govori istinu), te od tri osobe u nizu barem jedna govori istinu (inače bi srednja osoba u tom nizu imala dva susjeda koja lažu).

Očito u krugu postoji barem jedna osoba koja govori istinu i barem jedna osoba koja laže.

Promotrimo jednu osobu koja govori istinu. Ostalih $2022$ osoba podijelimo u $674$ trojki uzastopnih osoba. U svakoj takvoj trojki sjedi barem jedna osoba koja govori istinu (inače bismo imali tri uzastopne osobe koje lažu). Zato je broj osoba $N$ koje govori istinu barem $1+674=675$.

Promotrimo sada jednu osobu koja laže, i podijelimo ostalih $2022$ osoba u $1011$ parova susjednih osoba. U svakom paru sjedi barem jedna osoba koja laže (inače bismo imali dvije uzastopne osobe koje govore istinu). Zato je broj osoba $N$ koje govori istinu najviše $1011$.

Time smo dokazali da je nužno $675\leq N\leq1011$. Dokažimo da za svaki od tih izbora broja $N$ možemo naći povoljan razmještaj osoba u krugu.

Neka nekih sedam osoba u krugu zadovoljavaju ILLILIL, gdje slovo I označava osobu koja govori istinu, a L osobu koja laže. Ostalih $2016$ osoba podijelimo u $K$ šestorki uzastopnih osoba oblika ILILIL i $336-K$ šestorki oblika ILLILL.

Svaka takva konfiguracija zaista zadovoljava uvjete zadatka: pored svake osobe koja govori istinu sjedi osoba koja laže, a pored svake osobe koja laže sjedi barem jedna osoba koja govori istinu (uključujući i osobe koje dolaze na kraju šestorki, budući da će nakon nje doći niz osoba koje počinju osobom koja govori istinu).

Broj osoba koje govore istinu tada je jednak

$$N=3+K\cdot3+(336-K)\cdot2=675+K.$$

Kako broj $K$ može poprimiti bilo koju vrijednost iz skupa $\{0,1,\ldots,336\}$, konstruirali smo konfiguracije osoba među kojima je broj osoba koje govore istinu poprima svaku vrijednost iz skupa $\{675,676,\ldots,1010,1011\}$, što je i trebalo dokazati.