Odborný článek

O zebrách

29. 3. 2012 Základní vzdělávání
Autor
Mgr. Stanislav Novák

Anotace

Úlohy typu zebra (dále jen zebry) mají svůj původ v oblasti tzv. rekreační matematiky. Jedná se o logické hříčky, které trénují a utužují postupy logického uvažování, přinášejí radost z úspěšného vyřešení, ale hlavně se v nich nevyskytují žádná čísla – tradičně nepřátelsky vnímaní představitelé školské matematiky. V současnosti našly navíc zebry své pevné místo mezi úlohami testujícími tzv. obecné studijní předpoklady jedince. Získávají tak punc úloh, které zvládne vyřešit pouze člověk nadaný, ostatním pak zůstanou odpovědi na otázky typu „Kdo chová zebru?“ utajeny. (Svého času dokonce po internetu putovala tzv. Einsteinova zebra, kterou údajně dovedou vyřešit pouhá 2 % všech obyvatel planety Země [1]. Takové vnímání zeber je ještě posilováno tím, že úspěšný řešitel zpravidla dosahuje správné odpovědi intuitivně, s pomocí náčrtků, schémat nebo tabulek, kterým rozumí jen on sám a nikdo jiný. Nemalou část řešitelů odradí už samotná délka zadání úlohy, které může zabrat i několik řádků. V dalším textu se pokusíme zebry zbavit oné elitářské nálepky.

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 M1, M2, ..., Mm, 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 M1x M2 x ... x Mm , která má velikost n, a navíc platí, že každý prvek množiny Mi, 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 Mi, 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í:
M1= {Kapr, Mřínek, Vokoun, Cejn, Štika}
M2= {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 M1 a sloupce prvky množiny M2.

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 M1, M2, 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 Mi, 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í:
M1 = {Australan, Američan, Angličan, Francouz, Švéd}
M2 = {poušť, hory, údolí, moře, prales}
M3 = {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í:
M1 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 M1 jména farmářů.

M1 = {Albrecht, Bonifác, Cyril, Dařbuján, Evžen}
M2 = {Ben, Brok, Bull, Bax, Brix}
M3 = {ovce, kozy, krávy, koně, prasata}
M4 = {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 Mi, 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 M1 je umístěn v jiném sloupci prvního řádku schématu.
  • Všech n prvků množiny M2 je umístěno ve druhém řádku pod každým z prvků množiny M1 (druhý řádek tedy obsahuje m`*`n prvků).
  • Všech n prvků množiny Mn je umístěno v m-tém řádku pod každým z prvků množiny M1 (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 M1).
  •  uzly potencionální ... uzly, z nichž budeme vybírat pevné uzly (na počátku jsou potenciálními uzly všechny prvky množin Mi, 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 M1 – každá taková nápověda nám umožní označit vždy jeden z n potencionálních uzlů množiny Mi , 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.

Literatura a použité zdroje

[1] – UHLÍŘOVÁ, M. Logické úlohy známé - neznámé. 13. vydání. Praha : Prometheus, 2004.
[3] – Závitníček - Jak na "zebry". 2003. [cit. 2012-3-7]. Dostupný z WWW: [http://zavitnicek.sweb.cz/cla_zebry.htm].
Soubory materiálu
Typ
 
Název
 
pdf
231.45 kB
PDF
Zebra - Rybáři
pdf
231.45 kB
PDF
Zebra - Geologové
pdf
532.23 kB
PDF
Zebra - Farmáři

Licence

Všechny články jsou publikovány pod licencí Creative Commons BY-NC-ND.

Autor
Mgr. Stanislav Novák

Hodnocení od recenzenta

Tým RVP.CZ
29. 3. 2012
Velmi pěkně zpracovné téma. Lze využít v hodinách matematiky při společné práci učitele se žáky i pro samostatnou práci nadaných žáků.

Hodnocení od uživatelů

Článek nebyl prozatím komentován.

Váš komentář

Pro vložení komentáře je nutné se nejprve přihlásit.

Článek není zařazen do žádného seriálu.

Klíčové kompetence:

  • Základní vzdělávání
  • Kompetence k řešení problémů
  • samostatně řeší problémy; volí vhodné způsoby řešení; užívá při řešení problémů logické, matematické a empirické postupy
  • Základní vzdělávání
  • Kompetence k řešení problémů
  • ověřuje prakticky správnost řešení problémů a osvědčené postupy aplikuje při řešení obdobných nebo nových problémových situací, sleduje vlastní pokrok při zdolávání problémů
  • Základní vzdělávání
  • Kompetence k řešení problémů
  • vnímá nejrůznější problémové situace ve škole i mimo ni, rozpozná a pochopí problém, přemýšlí o nesrovnalostech a jejich příčinách, promyslí a naplánuje způsob řešení problémů a využívá k tomu vlastního úsudku a zkušeností