3. príklad - Vzorové riešenie
Zadanie
Na jednej z týchto papyrusových listín bol starostlivo nakreslený plán mesta. Štvorčeky na obrázku symbolizujú domy, keďže je ale dokument pár tisícročí starý, nezachovali sa na ňom informácie o jednotlivých obyvateľoch domov.
Vieme, že v každom z domov buď býval práve jeden človek, alebo v ňom žiaden človek nebýval. Ak v dome býval človek, tak aj vo všetkých domoch, do ktorých z neho ide šípka, býval človek. Ďalej vieme, že v každom riadku bývali aspoň 2 ľudia a v každom stĺpci boli aspoň dva domy neobývané. Nájdite všetky spôsoby, ako starovekí Egypťania mohli v meste bývať a dokážte, že žiadne ďalšie možnosti nie sú.
Vzorové riešenie
Zo zadania poznáme tri podmienky:
Ak v dome býval človek, tak aj vo všetkých domoch, do ktorých z neho ide šípka, býval človek.
V každom riadku bývali aspoň 2 ľudia.
V každom stĺpci boli aspoň dva domy neobývané.
Najprv sa pozrieme na prvý stĺpec a na políčka E1 a D1. Vieme, že ak by bol dom na E1 obývaný, vďaka šípkam (a podmienke číslo 1) by boli obývané postupne aj D1, C1, B1, A2, A1. Tu nám ale nastáva spor s treťou podmienkou - v stĺpci by nebol žiadny dom, ktorý je neobývaný. Podobne to platí aj pri D1. Postupne, vďaka šípkam by boli obývané aj C1, B1, A2, A1. Tu nám znova nastáva spor s treťou podmienkou - v stĺpci by mohol byť iba jeden dom neobývaný (E1). Z tohto vyplýva, že domy E1 a D1 obývané byť nemôžu.
Teraz sa pozrieme na políčko B3. Ak by to bolo obývané, tak vďaka šípkam a prvej podmienke by boli obývané aj nasledujúce domy: A3, A4, A5, B5, C5, C4, B4, C3, C2, B2, A2, A1 a B1 - všetky v riadkoch A, B, C okrem C1. Toto by viedlo k tomu, že by v každom stĺpci okrem prvého domy v riadku D a E museli byť neobývané, aby bola splnená tretia podmienka. Tu nám nastáva spor s druhou podmienkou, ktorá hovorí o riadkoch - v riadku D a E by ostal iba jeden dom, ktorý by mohol byť obývaný (E1 a D1), no musia byť aspoň dva. Z toho nám vyplýva, že dom B3 obývaný byť nemôže.
Tento poznatok použijeme pri dome B3. Z políčka C2 ide šípka do B3, takže ten je tiež neobývaný. Rovnako to platí aj pri poličkach C3 a D3.
V každom riadku musia byť aspoň dva domy obývané, čo znamená, že v riadku D musia aspoň dva zo zvyšných 3 voľných domov byť obývané. Vidíme, že ak by bol obývaný dom D4, tak by bol vďaka šípke aj D5 a potom aj E5 a E4. Ak by bol až D5, tak aj tak by bol obývaný aj D4, pretože vďaka šípkam by boli obývané postupne E5, E4 a napokon aj D4.
Z toho nám vyplýva, že D5 a D4 sú isto obývané, nakoľko len D2 nestačí a tieto dva sú obývané vždy spolu.
Teraz sa pozrime na 5. stĺpec, kde zatiaľ vieme, že D5 aj E5 sú obývané. Tu vidíme, že ak by A5 bolo obývané, boli by postupne obývané aj B5 a C5 - čiže žiadny dom by nebol neobývaný. Ak by bolo obývané B5, tak by bolo zároveň aj C5 - čiže len jeden dom by mohol byť neobývaný. Z tohto nám vyplýva, že A5 aj B5 sú neobývané. Aplikujme tu teraz to pravidlo o neobývaných domoch. Z toho nám vyplynie, že tým pádom aj A4, A3, B4 a C4 sú neobývané.
V riadkoch A, B a C nám teraz ostávajú vždy už len dva domy, ktoré podľa druhej podmienky o riadkoch musia byť obývané - sú to A1, A2, B1, B2, C1, C5.
Ak je obývaný dom C1, podľa šípok a prvej podmienky vidíme, že aj D2 a E3 musia byť obývané.
No a aby platilo stĺpcové pravidlo o stĺpci 2, dom E2 musí byť neobývaný, pretože A2,B2 aj D2 sú obývané, len C2 nie je.
Týmto sme sa dopracovali k nasledujúcemu riešeniu:
Iné riešenie nie je, pretože ako sme si dokázali, ak by sa akýkoľvek neobývaný dom premenil na obývaný, jedna z podmienok by neplatila. Tak isto, ak by sa nejaký obývaný dom premenil na neobývaný, jedna z podmienok by neplatila.
