Sciencemag.cz
Doporučujeme
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
