autor Continentaleurope, zdroj: Wikipedia, licence obrázku GFDL
autor Continentaleurope, zdroj: Wikipedia, licence obrázku GFDL

Úloha: Nekonečná loterie

V nekonečné loterii máme nekonečně mnoho pytlíků: jeden s číslem 1, druhý s číslem 2, třetí s číslem 3, čtvrtý s číslem 4 atd. V každém pytlíku je nekonečně mnoho losovacích míčků s přísluš­ným číslem.

Dostanete k dispozici velkou krabici. Do této krabice můžete vložit kolik chcete míčků z kterýchkoli pytlíků. Podmínka je jen jedna: celkový počet míčků musí být konečný.
Poté začnete míčky v krabici vyměňovat. Musíte vyjmout a zaho­dit jeden míček a nahradit jej libovolným počtem míčků s nižšími čísly. Zahodíte-li například míček s číslem 100, můžete do kra­bice přidat 10 milionů míčků s číslem 99, 17 miliard míčků s číslem 98 atd. Počet míčků, kterými nahradíte jediný míček s číslem 100, není tedy nijak omezen.
A tak musíte pokračovat. V každém kroku můžete vyjmutý a zahozený míček nahradit libovolnou kombinací jiných míčků za předpokladu, že jejich počet bude konečný a že ponesou nižší čísla než míček, který jste zahodili. Vyjmete-li míček s číslem 1, nemůžete jej nahradit žádnými míčky, protože míčky s nižšími čísly než 1 neexistují.
Pokud vám nakonec míčky dojdou a krabici vyprázdníte, pro­hráli jste. Pokud budete vytahovat míčky věčně – tj. pokud vám nikdy nedojdou – vyhráli jste.
Dá se v nekonečné loterii vyhrát? Pokud ano, jak?

/následuje řešení/
Vyhrát nemůžete. Nekonečná loterie vás pokaždé přinutí ode­brat všechny míčky.
Může se to zdát v rozporu s intuicí, uvážíme-li, že celkový počet míčků může v každém kroku narůst ohromným způsobem. Tento nárůst je však konečný; nekonečno není. Raymond Smullyan v roce 1979 dokázal, že pokaždé prohrajete. Jeho myšlenka je založena na udržování přehledu o největším čísle v krabici a sledování míčků s tímto číslem.
Nejprve předpokládejme, že největší číslo v krabici je 1. Všechny míčky pak mají číslo 1. Musíte tedy jeden po druhém odebrat všechny míčky – a to znamená, že prohrajete.
Nyní předpokládejme, že největší číslo v krabici je 2. Číslo 1 nelze vyřazovat donekonečna, protože míčky s ním nakonec do­jdou. V určité fázi tedy budete muset vyřadit jeden z míčků s čís­lem 2 a nahradit jej mnoha míčky s číslem 1. Počet míčků s číslem 2 se tím snížil. Počet míčků s číslem 1 narostl, je však stále konečný. Ani nyní nemůžete vyřazovat míčky s číslem 1 donekonečna. Na­konec tedy budete muset vyřadit další míček s číslem 2 a nahradit ji mnoha míčky s číslem 1. Počet míčků s číslem 2 se tím opět snížil. Čas od času budete muset vyřadit míček s číslem 2, takže vám nakonec míčky s číslem 2 úplně dojdou. Nyní však všechny míčky v krabici mají číslo 1 – a my již víme, že v takovém případě prohrajete bez ohledu na to, kolik míčků s číslem 1 v krabici je.
Dobře, tak tedy předpokládejme, že největší číslo v krabici je 3. Ovšem. míčky s čísly 1 a 2 nemůžete vybírat (a vyřazovat) donekonečna z důvodů, které jsme právě rozebrali. Proto nakonec budete muset vyřadit míček s číslem 3. Počet míčků s číslem 3 se o 1 sníží a stejným argumentem lze ukázat, že časem budete muset vyřadit další míček s číslem 3, a pak další a další, dokud vám míčky s číslem 3 úplně nedojdou. Krabice pak bude obsahovat pouze míčky s čísly 1 a 2, a v takovém případě prohrajete, jak jsme již ukázali.
Pokračujeme-li tímto způsobem, je jasné, že prohrajete, pokud největší číslo v krabici bude 4, 5, 6 a tak dále. To znamená, že prohrajete bez ohledu na to, jaké číslo je v krabici největší. Počet míčků v krabici je však konečný, takže musí existovat nějaké největší číslo.
Ať je, jaké chce, prohrajete!
Formálně se jedná o důkaz podle principu matematické in­dukce. Tento princip říká, že pokud nějaká vlastnost celých čísel n platí pro n = 1 a pokud z její pravdivosti pro kterékoli n vyplývá její pravdivost pro n + 1, pak platí pro všechna přirozená čísla. Zde se jedná o vlastnost „Je-li největší číslo v krabici n, pak prohrajete“.
Ověřme to. Pokud n = 1, je největším číslem v krabici 1 a pro­hrajete.
Nyní předpokládejme, že jsme dokázali, že pokud je největší číslo v krabici n, pak prohrajete. Předpokládejme, že největší číslo v krabici je n + 1. Nemůžete vyřazovat míčky s čísly n nebo menšími, protože víme, že při takovém postupu prohrajete – dojdou vám míčky s čísly n nebo menšími. Časem tedy budete muset vyřadit jeden z míčků s číslem n + 1, čímž se počet takových míčků sníží o 1. Ze stejného důvodu se tento počet musí snížit znova a znova. a nakonec vyřadíte všechny míčky s číslem n + 1. Nyní však všechny zbývající míčky mají číslo n nebo menší, takže prohrajete. Stručně řečeno: pokud je největším číslem v krabici n + 1, prohrajete. A to je zbývající krok, který bylo třeba provést při důkazu indukcí.
Hra může pokračovat tak dlouho, jak budete chtít, musí však skončit po konečném počtu tahů. Tento konečný počet ovšem může být tak velký, jak si budete přát.

Tento text je úryvkem z knihy:
Ian Stewart: Kabinet matematických kuriozit profesora Stewarta
Argo a Dokořán 2013
2. vydání 2017
O knize na stránkách vydavatele

obalka_knihy

Scintilátor – co to vůbec je?

Scintilátor – velmi zvláštní slovo, že? Málokdo by řekl, že označuje něco, s čím se …

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