Hra Bridg-It a důkaz sporem

Tuto neobvyklou hru vynalezl David Gal, profesor matematiky na Brownově univerzitě; prodává se pod obchodním jménem Bridg-It (Přejdi). Lze ji hrát na deskách různých rozměrů. Dále popsaná verze se snadno hraje na papíru s tužkami dvou různých barev. Je zábavnější než piškvorky!
Předpokládejme, že použijete červenou a černou tužku. Černou tužkou namalujete 12 koleček tvořících obdélník tak, jak ukazuje obrázek 1. Pomocí červené pastelky přidejte dalších 12 puntíků tak, jak ukazuje obrázek 2. (V těchto obrázcích jsou červené puntíky znázorněné jako stínovaná kolečka.) Obrázek 2 představuje samotnou desku pro hru.

Jeden hráč používá černou tužku, jeho protivník červenou. První hráč nakreslí svislou nebo vodorovnou čáru, která spojí dva sousední body jeho barvy. Druhý hráč pak udělá totéž – spojí dva sousední puntíky svojí barvy. Oba hráči se dále po tahu střídají, přičemž černý se pokouší vytvořit souvislou linii čar od horní řady černých puntíků ke spodní řadě. Černá linie nemusí být přímá; může se zakřivovat jakýmkoliv způsobem tak dlouho, až než spojí protilehlé strany desky. Červený se snaží vytvořit podobnou linii od levého sloupce červených puntíků ke sloupci červených puntíků na pravém konci. Oba samozřejmě také využívají svých čar k blokování cesty protihráče.
Hráč, který dojde ke konci své cesty jako první, vítězí. Na obrázku níže vyhrál červený (jeho čáry jsou vyznačené tečkováním).
Pokud oba hráči hrají racionálně, kdo z nich si vždy zajistí výhru?

Řešení

Hned několik zahajovacích tahů vede vždy k výhře bílého. Jednou z možností je spojit dva puntíky, které jsou nejblíž ke středu desky. Existuje příliš mnoho různých možností, jak se hra může vyvíjet, a nelze je všechny probrat, ale toto zahájení a následná pozorná hra přinesou vítězství.
Dokázat, že první hráč může při správné hře bez ohledu na velikost desky vždy zvítězit, lze zajímavým způsobem.
Jde to takto:
(1) Předpokládejme, že druhý hráč má strategii vedoucí k jisté výhře.
(2) První hráč nakreslí svou první čáru. Poté, co druhý hráč nakreslí svou čáru, postupuje první hráč, jakoby byl druhým hráčem a hraje podle jeho vítězné strategie.
(3) Čára, kterou nakreslil první hráč ve svém prvním tahu, nemůže jeho vítěznou strategii ovlivnit. Nijak nevadí, když tato čára není součástí vítězné strategie. Pokud je, pak v příslušný okamžik namísto této čáry udělá čáru někde jinde.
(4) Proto první hráč musí vždycky vyhrát.
(5) To však odporuje našemu úvodnímu předpokladu, že vyhrát může druhý hráč a má k dispozici vítěznou strategii. Tudíž tento předpoklad byl mylný.
(6) Hra nemůže skončit nerozhodně a pro druhého hráče neexistuje žádná strategie vedoucí k výhře. Musí tedy existovat vítězná strategie pro hráče prvního!
Tento důkaz, používaný také u jiných her než Bridge-It, je známým důkazem teorie her. Dokazuje, že pro prvního hráče existuje postup, jak vyhrát na desce každé velikosti, aniž by bylo přitom třeba znát samotný postup. Důkazu není snadné porozumět, je-li vysvětlen tak stručně jako zde, ale když se pořádně zamyslíte, mohl by snad být jasný. Matematikové jej nazývají existenční tvrzení – tímto způsobem se dokazuje, že něco existuje, aniž je řečeno, jak k příslušnému řešení dojít.
V tomto případě je úvaha použitá v důkazu známá jako reductio ad absurdum (důkaz sporem). Dokážete, že jedno ze dvou tvrzení musí být pravdivé, budete to předpokládat o jednom z nich, dojdete k logickému sporu (nesmyslu) – a proto musí platit to druhé tvrzení.
Zde důkaz probíhá následovně: (1) Jeden z hráčů musí vyhrát, (2) předpokládá se, že druhý hráč může vždy vyhrát, (3) tento předpoklad vede to k logickému rozporu, (4) tudíž může vždy vyhrát první hráč.

 

Tento text je úryvkem z knihy: Martin Gardner: Zábavné matematické hádanky
Nové vydání Dokořán 2023
O knize na stránkách vydavatele
obalka-knihy

Poznámka PH: Proč je uvedený důkaz hodně zjednodušený, co mu chybí, jak to zformulovat lépe? U jakého typu her lze tento důkaz použít (jaké podmínky musí být splněny), proč to nefunguje u dámy, u šachů (co piškvorky?)…

Co žere vesmír?

Vypadá to, jako by nějaký vesmírný obr ukousl z kosmu gigantické sousto, po kterém zbylo …

2 comments

  1. Jiří Gutman

    Pobavilo mne, že hrají červený a černý a vyhraje bílý :-).

  2. Pavel Houser

    tak tady je to temi cernobilymi ilustracemi, ale jinak to je tradicni problem, znama „cervena kralovna“ je sachova figurka puvodne 🙂

Napsat komentář

Vaše e-mailová adresa nebude zveřejněna. Vyžadované informace jsou označeny *

Používáme soubory cookies pro přizpůsobení obsahu webu a sledování návštěvnosti. Data o používání webu sdílíme s našimi partnery pro cílení reklamy a analýzu návštěvnosti. Více informací

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this.

Close