(c) Graphicstock

Dámy na obří šachovnici n x n

Kolika způsoby lze poskládat na normální šachovnici 8 dam, aniž by se vzájemně napadaly? Odpověď zní 92 (PH: předpokládám, že symetrie se počítají jako různé pozice, mají odlišnou šachovou notaci). A jak je to na obecné šachovnici n x n s n dámami?
Úlohy spojené s šachovnicí se v rekreační matematice těší docela oblibě, ale řeší se i v rámci matematiky míněné zcela vážně. Výše uvedený problém s 8 dámami byl zformulován v roce 1848 a najít odpověď tehdy trvalo několik let. Obecný problém n dam na šachovnici n x n se objevil v roce 1869. Michael Simkin z Harvardu jej vyřešil až na konci loňského roku, a to jde ještě jen o částečné řešení.
Odpověď zní, že existuje (0,143n) na n možností. Už z toho je jasné, že jde o řešení přibližné: výsledek nebude celé číslo, ale ani po zaokrouhlení (apod.) nemusí jít o správný výsledek. Také to má platit jen pro gigantické šachovnice (PH: no, pro 8 x 8 to opravdu nějak nevychází). Pro šachovnici milion krát milion vychází jako počet možných pozic číslo s asi 5 miliony číslic.
Samotná rovnice prý byla odvozena tak, že se problém řešil jako optimalizační – tj. zda dámy na gigantické šachovnice, (chceme-li, aby se nenapadaly, přirozeně) umísťovat spíše do centra nebo do krajních částí. Tato metoda vedla k odhadu dolní hranice, pak následovala metoda odhadu horní hranice („metoda entropie“). Uvedený vzorec popisuje „něco mezi“ oběma hranicemi, nicméně M. Simkin současně dokázal, že odhad dolní a horní hranice se při použití jeho metod kupodivu od sebe liší jen málo. K takovému výsledku alespoň došel po 5 letech studia problému. Samozřejmě se příslušný vzoreček možná ještě podaří nějak zpřesnit.
Úlohy tohoto typu s vlastní šachovou hrou už mají společného jen velmi málo, např. Simkin sám se označuje za velmi slabého šachistu. Naopak pro nematematika (bez ohledu na to, zda/jak hraje šachy) je to ale celé jen nepochopitelná kuriozita, ale snad alespoň trochu zajímavá…

Michael Simkin, The number of n-queens configurations. arXiv:2107.13460v2 [math.CO], arxiv.org/abs/2107.13460
Zdroj: Harvard University/Harvard Gazette/Phys.org

Voda v kráteru Gale na Marsu přetrvávala déle, než se myslelo

Mezinárodní tým vědců pod vedením Imperial College London objevil doklady otm, že v marsovském kráteru …

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