6. príklad - Vzorové riešenie

Kategórie:
5
6
7
8
9

Zadanie

Z hlbín vesmíru priletelo 100 bohov a posadalo si okolo jedálneho stola. Každý z nich buď hovorí pravdu, klame, alebo drieme. Driemajúcemu bohovi sa nechce rozmýšľať, preto vždy, keď ide niečo povedať, spýta sa boha po svojej ľavici, a aj tak to dopletie a povie opak. To znamená, že ak má po svojej ľavici pravdovravného boha, tak klame, a ak má po svojej ľavici klamára, tak hovorí pravdu. Ak boh po jeho ľavici tiež drieme, tak spanikári a vymyslí si odpoveď, ktorá môže byť aj pravdivá, aj nepravdivá. Keď sme sa bohov opýtali, kto sedí po ich pravici, každý z nich povedal, že je to klamár. Koľkí bohovia môžu byť klamári? Nájdite všetky možnosti.

Vzorové riešenie

Opravovali: Paľo, alica, merlin

Označme si klamára K, pravdovravného P a driemajúceho boha D.

Pozrime sa najskôr na prípad, že pri stole sedí aspoň jeden klamár. Napravo od neho nemôže sedieť K, lebo by o ňom tento klamár naľavo zaklamal, že je P alebo D, čo sa podľa zadania nestalo. Môžu byť od neho napravo jedine P a D. V oboch prípadoch sa môže stať, že K o nich povie, že sú klamári.
Vieme, že P hovorí vždy pravdu. Ak je napravo od K boh D, tak tento D bude hovoriť opačne ako K, teda bude hovoriť pravdu. Teda či už napravo od K je boh P alebo boh D, tento boh hovorí pravdu, keď tvrdí, že má napravo klamára. Preto ďalší boh napravo bude znova K. Pre tohto klamára môžeme úvahu zopakovať, napravo od neho bude P alebo D, napravo od tohto K.
Toto vieme opakovať, až kým sa nedostaneme okolo stola späť ku prvému klamárovi. Celý stôl tak vyzerá nejako takto:

K,\, P/D,\, K,\, P/D,\, K,\,... ,\, P/D,\, K,\, P/D

Ako vidíme, K je každý druhý. Dokázali sme tak, že ak je K aspoň jeden, je ich práve polovica z celkového počtu, čo je 100:2=50.

Ostáva nám jedine prípad, keď nie je pri stole ani jeden K. Napravo od P ale musí byť K, preto by pri stole nemôžu sedieť ani žiadni pravdovravní. Zostalo nám teda okolo stola posadiť 100 D bohov. Každý z nich má tak po svojej ľavici D, takže všetci spanikária a mohlo sa stať, že všetci zaklamali a povedali, že boh od nich napravo je klamár.

Odpoveď: Klamárov môže byť iba 0 alebo 50.

Komentár

Častou chybou v riešeniach bolo nesprávne pochopenie toho, ako funguje driemajúci boh. Potom niektoré časti dôkazu nefungovali pre správne zadanie, čo sa odzrkadlilo aj na bodoch. Chybám tohto typu sa dá vyvarovať dôkladným čítaním zadania. Ak vám niečo nie je jasné, môžete napísať do komentárov pod zadaním, vedúci vám odpovie.