2. príklad - Vzorové riešenie

Kategórie:
5
6

Zadanie

Marston sa rozhodol svoj prototyp detektoru lži preveriť v praxi na svojich kolegoch. V jeho práci je v rade vedľa seba niekoľko kancelárií (viac ako 1). V každej kancelárii sídli jeden kolega, ktorý buď vždy hovorí pravdu alebo vždy klame. Keď majú kolegovia kancelárie vedľa seba, nazývame ich susedia.

Marston sa svojich kolegov môže pýtať tieto otázky:

  • „Sú obaja tvoji susedia pravdovravní?“
  • „Sú obaja tvoji susedia klamári?“
  • „Je jeden tvoj sused pravdovravný a jeden klamár?“

Pokiaľ sa ale pýta niekoho, kto má kanceláriu na kraji (teda má len jedného suseda), tak sa môže spýtať iba, či je ten jeden sused pravdovravný alebo klamár.

Marston si môže ľubovoľne veľakrát vybrať jedného z kolegov a spýtať sa ho jednu z povolených otázok.

Pri akom počte kancelárií vie Marston určite zistiť, kto sú klamári a kto pravdovravní kolegovia? V prípadoch keď sa to dá, popíšte, ako to má spraviť, a keď sa to nedá, vysvetlite prečo.

Vzorové riešenie

Opravovali: mati

Prvé čo si vieme všimnúť, je že ak má ľubovoľný z Marstonových kolegov 2​ susedov, tak je práve jedno z nasledujúcich tvrdení pravdivé:

  • obaja jeho susedia sú klamári
  • obaja jeho susedia sú pravdovravní
  • práve jeden jeho sused je klamár a práve jeden jeho sused je pravdovravný

To je jasné :), ak obaja susedia Marstonovho kolegu sú pravdovravní, tak určite ani jeden z nich nie je klamár nie to ešte dvaja. Bezohľadu na to, ktorá z týchto situácií nastane Marston sa svojho kolegu môže opýtať všetky 3 otázky a ak je kolega pravdovravný, tak raz odpovie áno a dvakrát nie. Ak je klamár, tak dvakrát odpovie nie a raz áno. Vďaka tomu Marston dokáže o každom kolegovi, ktorý nie je krajný povedať, či je klamár, alebo pravdovravný.

Tak čo spravíme s krajnými kolegami?

Musíme rozlíšiť dva prípady:

Pokiaľ máme aspoň 3 ľudí na ktorých Marston skúšal svoj detektor lži, tak to je jednoduché. Spýtame sa krajného kolegu, či je jeho sused pravdovravný, a uvidíme či hovorí pravdu. Ak odpovie áno a jeho sused je skutočne pravdovravný, čo už vieme z prvej časti, alebo odpovie nie a jeho sused je skutočne klamár tak aj náš krajný kolega je pravdovravný. V opačnom prípade je klamár. Vďaka tomu ak máme aspoň 3 ľudí na ktorých testujeme detektor lži, tak vieme zistiť, kto je pravdovravný a kto je klamár.

Nakoniec ak máme ľudí iba 2, tak sme sa dostali do zložitej situácie. Nikto nemá dvoch susedov a teda nevieme o ňom priamo zistiť, či je pravdovravný, alebo klamár. Problém je, že ak sú obaja pravdovravní, aj ak sú obaja klamári, tak nám dávajú rovnaké odpovede. Rozlíšme kolegiňu Annu​ a kolegu Boba.

Najprv predpokladajme, že sú obaja klamári a postupne sa ich pýtajme otázky:

  • Marston: "Anna, je tvoj sused Bob klamár?", Anna: "Nie." (zaklamala).
  • ​Marston: "Anna, je tvoj sused Bob pravdovravný?", Anna: "Áno." (zaklamala).
  • Marston: "Bob, je tvoja susedka Anna klamárka?", Bob: "Nie." (zaklamal).
  • ​​Marston: "Bob, je tvoja susedka Anna pravdovravná?", Bob: "Áno." (zaklamal).

Teraz predpokladajme, že sú obaja pravdovravní a postupne sa ich pýtajme otázky:

  • Marston: "Anna, je tvoj sused Bob klamár?", Anna: "Nie." (hovorí pravdu).
  • ​Marston: "Anna, je tvoj sused Bob pravdovravný?", Anna: "Áno." (​hovorí pravdu).
  • Marston: "Bob, je tvoja susedka Anna klamárka?", Bob: "Nie." (hovorí pravdu).
  • Marston: "Bob, je tvoja susedka Anna pravdovravná?", Bob: "Áno." (hovorí pravdu).

Tým sme vyčerpali všetky možné otázky,  ktoré sa Anny a Boba môžeme spýtať, avšak nepodarilo sa nám zistiť, či sú obaja pravdovravní, alebo klamári, v oboch prípadoch odpovedajú rovnako.

Odpoveď: Pokiaľ Marton testuje detektor lži aspoň na 3 kolegoch, tak vie zistiť kto je klamár a kto je pravdovravný. Pokiaľ ho testuje iba na 2, tak nie.