Problém se zrny na šachovnici

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 13. prosince 2021; kontroly vyžadují 4 úpravy .

Problém zrn na šachovnici  je matematický problém , ve kterém se počítá, kolik zrnek bude na šachovnici , pokud na každou další buňku šachovnice položíte dvakrát více zrnek než na předchozí, počínaje od jedné.

Zpravidla je problém vyřešen pro standardní 64článkovou desku; když se počet zrn v každé následující buňce zdvojnásobí, je součet zrn ve všech 64 buňkách určen výrazem:

,

což je 18,446,744,073,709,551,615 .

Problém a jeho variace se používají k demonstraci vysoké rychlosti růstu exponenciálních sekvencí .

Původ problému

Přestože se detaily popisu úkolu v různých zdrojích liší, podstata zůstává stejná. Podle jedné z legend vynalezl šachy mudrc Sissa , který svůj vynález ukázal vládci země. Tomovi se hra tak líbila, že dal vynálezci právo vybrat si odměnu sám. Mudrc požádal krále za první buňku šachovnice, aby mu zaplatil jedno zrnko pšenice , za druhé dvě, za třetí čtyři a tak dále, přičemž počet zrn v každé další buňce zdvojnásobil. Vládce, který matematice nerozuměl, rychle souhlasil, byť poněkud uražen tak nízkým odhadem vynálezu, a nařídil pokladníkovi, aby vypočítal a dal vynálezci správné množství obilí. Když však o týden později pokladník stále nebyl schopen spočítat, kolik zrn je potřeba, zeptal se vládce, co je důvodem takového zpoždění. Pokladník mu ukázal výpočty a řekl, že není možné zaplatit, kromě odvodnění moří a oceánů a osetí celého prostoru pšenicí.

Množství obilí je asi 1800násobek světové sklizně pšenice za rok (v zemědělském roce 2008/09 byla sklizeň 686 milionů tun [1] ), to znamená, že převyšuje celou sklizeň pšenice za celou historii lidstva. . Počet zrn je přibližně 0,0031 % Avogadrova čísla . V jednotkách hmotnosti: pokud předpokládáme, že jedno zrno pšenice má hmotnost 0,065 gramu (troyské zrno : 1 gr \u003d 0,06479891 zrna ) , pak celková hmotnost pšenice na šachovnici bude 1200 miliard tun nebo 1,2 bilionu tun:

.

Možnosti

Existuje podobný problém, ve kterém král žádá velitele, aby každý den sbíral minci dvakrát větší než ta předchozí. Jakov Perelman v knize „Živá matematika“ [2] uvádí následující verzi problému, jehož zápletka je podle něj vypůjčena ze „starého latinského rukopisu“: když se statečný velitel vrátil z bojů do Říma , tak se střídavě střílelo a střílelo. císař se zeptal, jakou platbu chce za svou službu. Velitel požádal o nebetyčně vysokou částku. Císař, aby nebyl považován za lakomce nebo člověka, který nedodrží slovo, navrhl veliteli, aby druhý den šel do pokladnice a vzal si jednu měděnou minci v nominální hodnotě jedné prsa (o hmotnosti pět gramů), tzv. den později - dvě prsa, pak čtyři atd., dokud si přijaté mince sám odnese (každý den se odlévají mince požadované hmotnosti). Velitel, který se rozhodl, že by mohl snadno zbohatnout, souhlasil. Osmnáctého dne však již nebyl schopen minci odnést a v důsledku toho dostal jen malou část odměny, kterou od císaře požadoval.

Podle jiné verze uzavřeli dva obchodníci dohodu, že po dobu jednoho měsíce bude první dávat druhému 10 000 $ denně . Druhý musí první den vrátit jeden cent prvnímu , druhý dva centy atd. Druhý obchodník souhlasil a první tři týdny byl spokojený s příjmem, ale na konci měsíce byl úplně zničený a dal celý svůj majetek prvnímu. Perelman uvádí verzi, podle níž první člověk nedává 10 000, ale 100 000 denně (v ruských peněžních jednotkách), ale výsledek se výrazně nemění.

V jiné verzi si člověk koupí koně, ale je nespokojený s cenou 1000 rublů. Prodejce mu nabídne, že nezaplatí za koně, ale za hřebíky do podkovy, za prvního polovinu , za druhého dvě, za třetí haléř a tak dále. Vzhledem k tomu, že v každé podkově je 6 hřebíků, je kupující nucen zaplatit více než 40 tisíc rublů.

Druhá polovina šachovnice

Ve strategické technologii je „druhá část šachovnice“ fráze vytvořená Rayem Kurzweilem ve vztahu k bodu, kdy exponenciální růst určitého faktoru začíná mít významný ekonomický dopad na celkovou ekonomickou strategii podniku. Zatímco počet zrn na první polovině desky je velký, na druhé polovině je počet mnohonásobně větší. Počet zrnek na první polovině desky je 1 + 2 + 4 + ... + 2 147 483 648 , celkem 2 32 - 1 = 4 294 967 295 zrn , neboli cca 100 tun rýže o váze jedno zrno 25 mg [3] . To je přibližně 1/1200000 z celkového množství rýže pěstované v Indii za rok (údaje za rok 2005) [4] .

Množství zrn na druhé polovině desky je 2 32 + 2 33 + 2 34 ... + 2 63 \u003d 2 64 - 2 32 zrnek rýže . Jen na 64. čtverci hrací plochy bude 263 = 9223372036854776808 grainů , více než 2 miliardkrát více než na celé první polovině desky. Na celé desce bude 2 64-1 = 18 446 744 073 709 551 615 zrn , jejich celková hmotnost bude 461 168 601 842,7  tun .

Poznámky

  1. ↑ International Grains Council (IGC). Přehled trhu s obilím . Získáno 17. února 2011. Archivováno z originálu 24. listopadu 2010.
  2. ↑ Perelman, 1967 .
  3. ↑ Rice CRC …velikost a hmotnost
  4. ↑ Rice Policy – ​​IRRI World Rice Statistics (WRS) Archivováno 16. září 2008 na Wayback Machine

Literatura

Odkazy