Županijsko natjecanje 2023., 1. razred SŠ, A varijanta, 5. Zadatak
U krugu sjede osobe. Među njima je osoba koje uvijek govore istinu, dok svi ostali uvijek lažu. Svi su dali izjavu: „Obje osobe koje sjede do mene lažu.” Odredi sve vrijednosti broja za koje je to moguće.
Rješenje
Dokazat ćemo da može poprimiti bilo koju vrijednost iz skupa
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 osoba podijelimo u 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 koje govori istinu barem .
Promotrimo sada jednu osobu koja laže, i podijelimo ostalih osoba u 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 koje govori istinu najviše .
Time smo dokazali da je nužno . Dokažimo da za svaki od tih izbora broja 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 osoba podijelimo u šestorki uzastopnih osoba oblika ILILIL i š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
Kako broj može poprimiti bilo koju vrijednost iz skupa , konstruirali smo konfiguracije osoba među kojima je broj osoba koje govore istinu poprima svaku vrijednost iz skupa , što je i trebalo dokazati.
Napomena: Rješenje prati sljedeću bodovnu shemu: bod za točan skup vrijednosti broja , bodova za dokaz da se mora nalaziti u tom skupu, te boda za konstrukciju takvih grupa osoba za svaki .
Moguće je dokazati sljedeću tvrdnju: između svake dvije uzastopne osobe koje govore istinu (između kojih ne postoji treća osoba koja govori istinu) sjedi jedna ili dvije osobe koje lažu. Iskaz i dokaz te tvrdnje nosi bod (koji odgovara drugom bodu gornje sheme).
Za zadnja boda nije dovoljno dati primjer osoba za rubne slučajeve i , nego i za sve između. Konstrukcija za te rubne slučajeve nosi po bod, te jasan i nedvosmislen opis konstrukcije svih ostalih slučajeva nosi bod. Ova tri boda ne zbrajaju se sa zadnja boda iz gornje bodovne sheme.