O zebrách

Anotace

V každé zebře jde zjednodušeně o to, že máme několik stejně velkých množin prvků (pojmů), které musíme seskupit tak, aby to vyhovovalo všem podmínkám (nápovědám) formulovaným v zadání. K vyřešení nám mohou být předloženy zebry jednoduché i obtížnější, je-li však zebra správně sestavena, není neřešitelná. Obtížnost zebry je určena především dvěma parametry:

• m ... počet množin pojmů

• n ... velikost množin pojmů

Je-li dáno m různých množin M₁, M₂, ..., M_m, z nichž každá obsahuje právě n prvků, mluvíme o zebře typu mxn (dále jen zebra (mxn)). Jazykem teorie množin pak lze říci, že řešením zebry (mxn) je podmnožina Z kartézského součinu M₁x M₂ x ... x M_{m ,} která má velikost n, a navíc platí, že každý prvek množiny M_i, kde `iin` {1,2, ... m}, se vyskytuje v právě jedné m-tici z množiny řešení Z. Na tuto vlastnost se v dalším textu budeme odkazovat jako na princip zebry.

Dalším faktorem, který ovlivňuje obtížnost zebry, je způsob formulace nápověd (podmínek), které jsou nedílnou součástí zadání. Jsou formulovány v jednoduchých oznamovacích větách či souvětích (která lze na jednoduché věty rozložit). Kvalitativně můžeme rozlišit dva typy podmínek:

• pozitivní ... mají tvar kladné oznamovací věty (př: Pudl patří majiteli modrého auta.)

• negativní ... mají tvar záporné oznamovací věty (př: Pěstitel slunečnic nepije vodu.)

V dalším poznáme, že obtížněji se do řešení zapracovávají negativní nápovědy.

Obecné zásady řešení

Prvním úkolem při řešení zebry je odhalit v zadání množiny M_i, kde i`in` {1, 2, ... m} a všechny jejich prvky. V dalším kroku pracujeme se zadanými podmínkami – snažíme se je přeformulovat do jednoduchých oznamovacích vět (pokud v tomto tvaru již nejsou) a pro lepší orientaci jednotlivé nápovědy očíslujeme. Další postup závisí na zvolené metodě řešení. V následující části si připomeneme dvě již popsané metody řešení a popíšeme původní metodu, která se ukáže být nejuniverzálnější. Každá metoda je ilustrována řešením konkrétní úlohy.

Metoda 1: Tabulka

Nejjednodušší zebry bývají typu 2xn, kde nejčastěji n`in`{4, 5, 6}. Pro řešení těchto zeber se jako nejvýhodnější strategie jeví záznam do tabulky formátu nxn, což je dáno také tím, že množinu řešení Z tvoří právě n uspořádaných dvojic, které lze tabulkou pohodlně zachytit.

Příklad 1: Zebra (2x5) –Rybáři

Pět rybářů se vydalo na lov. Jmenovali se Kapr, Mřínek, Vokoun, Cejn a Štika. Každý z nich chytil jednu rybu. Tyto ryby byly shodou okolností stejného jména, jako byla jména rybářů. Nikdo však nechytil rybu, jejíž jméno nesl. Pan Cejn nechytil Štiku a pan Štika nechytil cejna. Štiku ulovil jmenovec ryby, kterou chytil pan Vokoun, nebyl to ale kapr. Toho nechytil ani pan Štika. Jakou rybu ulovil pan Kapr? [2]
    
řešení:
M₁= {Kapr, Mřínek, Vokoun, Cejn, Štika}
M₂= {kapr, mřínek, okoun, cejn, štika}

Přeformulování podmínek zadání:

1. Pan Kapr nechytil kapra.
2. Pan Mřínek nechytil mřínka.
3. Pan Vokoun  nechytil okouna.
4. Pan Cejn nechytil cejna.
5. Pan Štika nechytil štiku.
6. Pan Cejn nechytil štiku.
7. Pan Štika nechytil cejna.
8. Štiku ulovil jmenovec ryby, kterou chytil pan Vokoun
9. Pan Vokoun nechytil kapra.
10. Štiku neulovil pan Kapr.
11. Pan Štika nechytil kapra.

Sestavení tabulky – tabulka 5x5 (tabulka 1), kde řádky jsou označeny prvky množiny M₁ a sloupce prvky množiny M₂.

Vyplňování tabulky – na základě očíslovaných nápověd vyplňujeme tabulku dvěma symboly:

• X ... uspořádaná dvojice nepatří do množiny Z.

• OK ... uspořádaná dvojice patří do množiny Z.

tabulka 1 – Autor díla: Stanislav Novák

U některých symbolů v tabulce jsou čísla podmínek zadání, podle nichž byly doplněny. Není-li číslo uvedeno, byl symbol doplněn na základě principu zebry.

odpověď: Pan Kapr ulovil cejna.

Metoda 2: Konstrukce kružnic

Metoda řešení tabulkou však selhává již u zeber (3xn) – je zde použitelná, ovšem na úkor přehlednosti a elegance řešení [1]. V tomto případě se efektivnější ukazuje metoda vycházející z teorie grafů. Jednotlivé prvky množin M₁, M₂, _M3 tvoří uzly, mezi nimiž konstruujeme hrany na základě podmínek v zadání – úspěšného řešení dosáhneme tehdy, podaří-li se nám zkonstruovat právě n kružnic obsahujících právě 3 uzly, z nichž každý patří do jiné množiny M_i, kde i`in` {1, 2, 3}.

Příklad 2: Zebra (3x5) – Geologové

Pět geologů se vybralo do různých oblastí, aby tam pátrali po nových nalezištích. Každý muž byl jiné národnosti a našel jiný druh nerostného bohatství v jiném typu krajiny:

1. Australan zkoumal poušť.
2. Naftu našel Američan.
3. Železo bylo v horách.
4. Zlato nenašel Australan.
5. Angličan hledal v údolí řeky.
6. Francouz narazil na diamanty.
7. Diamanty nebyly na mořském dně.

Odpovězte na tyto otázky:

1. Co bylo v pralese?
2. Kde se našly opály?
3. Co bylo na mořském dně?
4. Co objevil Švéd?

řešení:
M₁ = {Australan, Američan, Angličan, Francouz, Švéd}
M₂ = {poušť, hory, údolí, moře, prales}
M₃ = {nafta, železo, zlato, diamanty, opály}

Přeformulování podmínek zadání – podmínky zadání jsou v požadovaném tvaru

Všechny prvky jednotlivých množin rozmístíme pohromadě po obvodu rovnostranného trojúhelníku (viz obrázek 1). Tyto prvky tvoří uzly konstruovaných grafů – v průběhu řešení budeme mezi uzly konstruovat dva typy hran v závislosti na formulaci nápovědy:

• pozitivní ... plná hrana – dané dva uzly patří do jedné uspořádané trojice z množiny řešení Z
• negativní ... přerušovaná hrana – dané dva uzly nepatří do jedné uspořádané trojice z množiny řešení Z

obrázek 1 – Autor díla: Stanislav Novák

U některých hran grafu je číslo podmínky zadání, podle níž byla sestrojena. Není-li číslo uvedeno, byla hrana sestrojena na základě principu zebry. Při řešení na papíře si můžeme „použité“ nápovědy škrtat.

odpovědi:

1. V pralese byly diamanty.
2. Opály se našly v poušti.
3. Na mořském dně byla nafta.
4. Švéd objevil železo.

Metoda 3: Hledání cesty

Zvýšíme-li obtížnost a zaměříme se na zebry (4xn), metoda konstrukce kružnic také nestačí (některé podmínky zadání mohou vést ke konstrukci hrany uvnitř očekávané kružnice obsahující tentokrát 4 uzly). Přesto lze nalézt metodu inspirovanou teorií grafů, která přehledně a spolehlivě vede ke správnému řešení jakékoliv zebry. Algoritmus této metody bude nastíněn v další části textu a ilustrován původním příkladem zebry (5x5).

Příklad 3: Zebra (5x5) – Farmáři

Na venkově vedle sebe leží pět farem. Každou farmu vlastní právě jeden z pěti mužů, každý z nich má jiného psa, pěstuje jinou plodinu a chová jiný druh hospodářských zvířat. Navíc každý muž využívá ke své práci na farmě jiný dopravní prostředek. Odpovězte na tři otázky, pokud víte následující:

1. Brixův pán chová kozy.
2. Traktorista chová kozy.
3. Majitel Bena pěstuje mrkev.
4. Cyril řídí dodávku.
5. Chovatel ovcí nejezdí traktorem.
6. Řidič pick-upu pěstuje víno.
7. Bonifácův pes je Brix.
8. Baxův pán se jmenuje Dařbuján.
9. Řidič jeepu chová prasata.
10. Pěstitel vína nechová prasata.
11. Chovatel koní má psa Bulla.
12. Pěstitel brambor řídí jeep.
13. Chmel je svážen náklaďákem.
14. Evžen pěstuje chmel.
15. Albrecht chová ovce.

Odpovězte na tyto otázky:

1. Kdo chová krávy?
2. Kdo pěstuje mák?
3. Čí je Brok?

řešení:
M₁ nechť neobsahuje pojmy, které se v podmínkách zadání nevyskytují, ale vyskytují se pouze v otázkách. V našem případě zvolíme jako prvky množiny M₁ jména farmářů.

M₁ = {Albrecht, Bonifác, Cyril, Dařbuján, Evžen}
M₂ = {Ben, Brok, Bull, Bax, Brix}
M₃ = {ovce, kozy, krávy, koně, prasata}
M₄ = {mrkev, mák, brambory, chmel, víno}
M5 = {jeep, pick-up, traktor, náklaďák, dodávka}

Přeformulování podmínek zadání – podmínky zadání jsou v požadovaném tvaru.

Postup řešení metodou hledání cesty spočívá v konstrukci jednoduchého schématu obsahujícího pouze prvky množin M_i, kde i `in`{1, 2, ..., m}. Mezi těmito prvky (uzly) budeme následně konstruovat hrany podle informací z nápověd.

Schéma je složeno z právě m řádků a n sloupců (viz obrázek 2):

• Každý z n prvků množiny M₁ je umístěn v jiném sloupci prvního řádku schématu.
• Všech n prvků množiny M₂ je umístěno ve druhém řádku pod každým z prvků množiny M₁ (druhý řádek tedy obsahuje m`*`n prvků).
• Všech n prvků množiny M_n je umístěno v m-tém řádku pod každým z prvků množiny M₁ (m-tý řádek tedy obsahuje mn prvků).

Schéma Farmářů vypadá následovně (v průběhu řešení v časové tísni je praktičtější nahradit celé pojmy srozumitelnými, ale jednoznačnými zkratkami – viz poslední řádek s dopravními prostředky):

obrázek 2 – Autor díla: Stanislav Novák

 
Ve schématu nalezneme uzly dvojího druhu:

• uzly pevné ... uzly, které tvoří hledanou cestu (na počátku jsou pevnými uzly pouze prvky množiny M₁).

•  uzly potencionální ... uzly, z nichž budeme vybírat pevné uzly (na počátku jsou potenciálními uzly všechny prvky množin M_i, kde i `in `{2, 3, ..., m}).

Postup řešení spočívá v zaznamenávání informací z nápověd do připraveného schématu v duchu následujících zásad (viz obrázek 3):

•  Začneme pozitivními nápovědami, které obsahují prvky množiny M₁ – každá taková nápověda nám umožní označit vždy jeden z n potencionálních uzlů množiny M_i , kde i {2, 3, ..., m}, za uzel pevný.

• Pokud se nacházejí dva pevné uzly ve sloupci pod sebou v bezprostředně sousedících řádcích, sestrojíme mezi nimi hranu jedné z hledaných cest.

obrázek 3 – Autor díla: Stanislav Novák

U některých uzlů grafu je číslo podmínky zadání, podle níž byly označeny za pevné uzly nebo odstraněny z množiny potencionálních uzlů. Není-li číslo uvedeno, byl úkon proveden základě principu zebry.

Zbylé pozitivní nápovědy a všechny negativní nápovědy pak do zjednodušeného schématu zaznamenáme odstraněním daných potencionálních uzlů, které se podle podmínek nemohou stát uzly pevnými. V průběhu práce se schématem využíváme principu zebry tak, že zbude-li nám na průsečíku sloupce a řádku schématu právě 1 z n původních potencionálních uzlů, označíme ho za uzel pevný a z dalších sloupců ho v daném řádku odstraníme.

Úloha je vyřešena, vznikne-li nám ve schématu po zaznamenání nápověd právě n cest, z nichž každá obsahuje právě m pevných uzlů. Následně budeme uzly jednotlivých cest interpretovat jako uspořádané m-tice, které náleží do množiny řešení Z.

odpovědi:

1. Krávy chová Cyril.
2. Mák pěstuje Bonifác.
3. Brok je Albrechtův.

Metoda hledání cesty se ukazuje být nejuniverzálnější ze všech zde uvedených, neboť není limitována ani počtem množin pojmů m, ani počtem jejich prvků n. Může však selhat, bude-li zadána zebra, jejíž podmínky zadání nebude možné do schématu jednoduše zaznamenat (podmínky například mohou mít podobu implikace). Takovým zebrám bude v budoucnu věnován samostatný článek.

Podrobná řešení všech tří úloh uvedených v článku jsou k dispozici jako přílohy.