Magický čtverec je takový čtverec (šachovnice) políček N x N, kde každé políčko obsahuje právě jedno jiné číslo (typicky od 1 do N²) a platí, že součet každého řádku, každého sloupce i obou diagonál je stejný - roven [ N * (N²+1) ] / 2.

Vhnízděný magický čtverec (nested magic square) je magický čtverec, jehož každý středově souměrný podčtverec, je také magický (součty řádků, sloupců a diagonál dávají však logicky jiný součet než u čtverce původního).

Velmi zajímavé čtení v češtině o magických čtvercích najdete zde a vyčerpávající údaje má pochopitelně Wikipedia.

Společný algoritmus - sudé i liché čtverce

Autorem algoritmu je Samavedula sita Rama Sastry. Zvlášť se konstruují sudé a liché magické čtverce. Základní princip je společný pro obě varianty: vyplňuji postupně jednotlivá barevná čtvercová pásma (viz obrázek), počínaje nejvnějším a konče nejvnitřnějším pásmem. První číslo, které do pásma umístím, označme fN (jako firstNumber) - na začátku pro nejvnější pásmo je =1. Podle níže uvedených pravidel vždy vyplním prvních 2*X - 2 čísel (tedy čísla fN, fN+1, fN+2, ... , fN + 2*X - 3), kde X je rozměr pásma, které právě vyplňuji (na začátku je X = N, kde N je rozměr původního čtverce). Jakmile umístíme tato čísla, dopočítáme osově protilehlá čísla pomocí doplňku do N²+1 (vyjímku tvoří ze mně neznámého důvodu doplňování rohů posledního řádku lichého řádu, kdy je zapotřebí tato čísla prohodit, tedy doplňovat nikoliv osově souměrně ale středově souměrně). Jakmile mám vyplněné celé pásmo, vnořím se a začnu pracovat se čtvercem o 2 menším. V tu chvíli se novým fN stává původní "fN + 2*X - 2" a novým rozměrem pásma X bude původní "X - 2".

Liché čtverce

Algoritmus je velmi jednoduchý a lze lehce odsledovat z výše uvedeného animovaného vzoru. Číslo fN přijde do 1. sloupce a 2. řádku. Postupně umísťuji lichá čísla fN+2, fN+4, fN+6... tak, aby prvních floor(X/2)-1 čísel počínaje fN bylo pod sebou v levém sloupci (floor je funkce ořezávající desetinná místa), prostřední liché číslo (fN + 2*X - 3)/2 - 1 padne do prostřeního sloupce a posledního řádku, a zbylá lichá čísla vyplníme hezky pod sebe do posledního sloupce počínaje prostředním řádkem.

Sudá čísla fN+1, fN+3, fN+5... umísťujeme za sebe bez prostředního sloupce tak, že začnem ve 2. sloupci posledního řádku číslem fN+1, skončíme před prostředním sloupcem a pokračujeme v 1. řádku hned za prostředním sloupcem. Poslední 2 sudá čísla padnou do rohů horní řádky počínaje nižším vlevo. Všechny výše uvedené adresace řádků a sloupců jsou vztaženy relativně k právě vyplňovanému pásmu nikoliv k původnímu čtverci NxN. Při dopňování do N²+1 nezapomeňte na prohození rohů v posledním řádku.

Sudé čtverce

Číslo fN přijde opět do 1. sloupce a 2. řádku. Není-li řád pásma dělitelný 4mi, pak číslo fN+1 přijde do 2. sloupce a 1. řádku. V obou případech pak pokračujeme v umísťování čísel [fN+1 když dělitelné 4,] fN+2, fN+3 tak, že první číslo padne do 3.řádku posledního sloupce a po dvojicích střídají strany (1. a poslední sloupec) až do předposledního řádku. Viz animovaný vzor. Dále umístíme poslední 2 čísla (fN + 2*X - 4) a (fN + 2*X - 3) do rohů horní řádky počínaje nižším vlevo. Nyní přijde nejtěžší část algoritmu.

Potřebujeme umístit (X - 2 - Top) čísel do dolního a horního řádku tak, aby platilo, že součet čísel v hroním řádku je stejný jako součet čísel v dolním řádku a aby počet čísel v obou řádcích byl stejný. Top je příznak umístění horního čísla fN+1, tedy je 0 pro řád dělitelný 4mi a je 1 pro řád nedělitelný 4mi. Pozor vždy uvažujeme obě rohová čísla v horním řádku a případné číslo fN+1 pro pásmo nedělitelný 4mi. První číslo, které nám zbývá do obou řádků umístit je U1 = (fN - 2 + X + Top) a poslední číslo /již umístěné/ je U2 = (fN + 2*X - 3). Odsud plyne, že součet každého řádku je (označme) SumU = [ ( U2 * (U2+1) - U1 * (U1-1) )/2 ) + Top * (fN + 1) ] / 2. Lehce spočítáme, že do dolního řádku musíme umístit přesně X/2 čísel, tak aby jejich suma byla = SumU. A začíná malá alchymie.

Představíme si řadu čísel zbývajících umístit seřazenou vzestupně:
(fN - 2 + X + Top), (fN - 1 + X + Top), (fN + X + Top), ... , fN + 2*X - 5
Nejlépe se to předtavuje pro čtverec 10x10: dostáváme řadu (X - 2 - Top) čísel: 10, 11, 12, 13, 14, 15, 16
Nyní přijde algoritmus, který vždy sečte posledních X/2 čísel z této řady (12+13+14+15+16 = 70) a porovná toto číslo s cílovou sumou SumU ( [(18*19-10*9)/2 + 1*2] / 2 = 64 ). Pokud je součet větší než cílová suma, pak vyjme K-té číslo z řady a dá jej na začátek řady. K je na začátku algoritmu rovno X/2-1-Top (v našem příkladu K=3, tedy beru třetí číslo v řadě, poprvé tedy beru 12), odpovídá tedy prvnímu číslu z posledních X/2 čísel, které sčítám. Algoritmus se pak opakuje, začnu znovu sčítat.

Pokud protočím všech K kombinací a nikdy součet není roven SumU, potom zvětším číslo K o jedno a celý algoritmus opakuji.

Výsledkem je tedy řada 10, 11, 12, 15, 16, jejíž součet je cílových 64. Zbývající čísla z řady umístím do 1. sloupce a jsem hotov. Všechny výše uvedené adresace řádků a sloupců jsou vztaženy relativně k právě vyplňovanému pásmu nikoliv k původnímu čtverci NxN.

Celý program najdete jako MAKRO v Excelu zde. Nebo si stáhněte javascript verzi.

Pakoválec jsem si koupil za 100 Kč 12.9.2004 na výstavě hlavolamů v kulturním domě na Vltavské, Bubenská 1, Praha 7. V té dově probíhala soutěž o 10.000 Kč. Jelikož jsem tehdy jezdil často vlakem na chatu - pomáhat tátovi stavět novou elektrickou kapličku (rozvodník), měl jsem dost času, abych na řešení přišel. A tak jsem poprvé v životě něco vyhrál vlastním přičiněním.

Moje řešení:

1. Nechť vrchní strana složeného hlavolamu je ta, ve které vidíme proti směru hodinových ručiček tyto barvy: žlutá, díra, červená, díra, modrá, zelená, díra a díra.
2. Očíslujme si řady od shora dolů čísly 1. až 4.
3. Vyšší řada oproti jiné nižší řadě je ta, která je položena výše, tedy má nižší pořadové číslo.
4. Skládáme od zdola nahoru (protože mi to tak přijde logičtější). Začínáme tedy 4. řadou.
5. Každou řadu kromě 1. lze složit pouze za pomocí vyšších řad, za předpokladu, že všechny nižší řady jsou již složeny.
6. Řekneme, že některá řada má kurzor, pokud průhledný pás pakoválce je v takové pozici, že s touto řadou otáčí
7. Pozice dvojice nazvěme v každé řadě pozici těch dvou kostiček, které spolu sousedí a nepodléhají posunu při změně kurzoru z této řady (při složeném pakoválci odpovídá pozici modré a zelené)
8. Pásmem barvy X nazvěme ten sloupec kostiček, který při složeném pakoválci odpovídá dané barvě X
9. Otočit kurzorem doprava znamená otočit kurzorem proti směru hodinových ručiček při pohledu shora

10. Složení řady 2.-4.:
    1. Nejprve usadíme pozici žluté a červené kostičky.
       1. žlutou kostičku nasadíme místo levé kostičky pozice dvojice - z některé vyšší řady nasuneme kurzorem žlutou těsně vlevo od pozice dvojice a otočíme o jedno vpravo)
       2. kurzorem odjedeme do vyšší řady
       3. červenou kostičku nasadíme hned vpravo od pozice dvojice (nasuneme kurzorem shora z některé vyšší řady)
       4. kurzorem otočíme doprava o 3 kostičky, aby žlutá i červená byly na svých místech (ve svém pásmu)
    2. Poté nastavíme modrou a zelenou kostičku
    1. modrou kostičku nasuneme shora z některé vyšší řady kurzorem vpravo těsně vedle pozice dvojice
    2. kurzorem otočíme o dvě kostičky vpravo a změníme kurzor na vyšší řadu (modrá kostička je v pásmu, kam patří žlutá)
    3. z některé vyšší řady nasuneme kurzorem zelenou kostičku vlevo od pásma červené barvy (bude zprava sousedit s připravenou zelenou) a otočíme kurzorem o 2 vlevo
    4. kurzor i s nastavenou dvojicí modrá-zelená přemístíme do některé vyšší řady a otočíme vlevo o 2 tak, aby tato dvojice odpovídala pozici dvojice
    5. kurzor přemístíme do řady, kterou skládáme, a otočíme vpravo o 2 kostičky
    6. kurzor vrátíme do řady, kde jsme nechali dvojici modrá-zelená a otočíme vpravo o 2 kostičky
    7. dvojici modrá-zelená nasuneme do skládané řady (vpravo těsně vedle pozice dvojice) a otočíme o 2 kostičky vlevo
    8. řada je složena

11. Složení 1. řady:
    1. dočasně obětujeme jednu z nižších řad (označme ji jako řadu pomocnou), abychom tuto 1. složili (doporučuji obětovat 4.)
    2. Usadíme žlutou a červenou kostičku v 1. řadě a to tak, že nerozhodíme žlutou a červenou v pomocné řadě.
       1. z 1. řady nasuneme kurzorem do pomocné řady červenou kostičku vpravo těsně vedle pozice dvojice
       2. pokud se nyní žlutá kostička ocitla těsně vedle pozice dvojice vlevo, vrátíme zpět kurzor nahoru (tudy cesta nevede) a pokračujeme bodem VII.
       3. jinak otočíme kurzorem o 2 kostičky vlevo a vrátíme se kurzorem do 1. řady
       4. do pomocné řady nasuneme žlutou kostičku těsně vpravo od červeného pásma a otočíme o 3 kostičky vpravo
       5. kurzor vrátíme do 1. řady a otočíme o 1 kostičku vlevo (žlutá i červená se tím ocitne v 1. řadě ve svém pásmu)
       6. kurzor přemístíme zpět dolů do pomocné řady a otočíme o 2 vpravo (žluté i červené pásmo je tím celé sestavené)
       7. [pokračování z bodu II.] - např. takto: umístíme červenou kostičku do červeného pásma a kurzor dáme do pomocné řady
       8. kurzorem otočíme o 2 kostičky vlevo a přemístíme do 1. řady, kde otočíme o 3 kostičky vlevo
       9. kurzor přemístíme do pomocné řady, otočíme doprava o 2 kostičky, přemístíme zpět nahoru a otočíme o jedno vpravo [konec pokračování]
    3. Nyní máme složené žluté a červené pásmo.
    4. Modrá a zelená kostička v 1. a pomocné řadě jsou však nejspíše rozhozené.
    
    5. Usadíme modrou i zelenou kostičku do obou rozhozených řad tím, že nikdy neporušíme vzdálenost žluté a červené kostičky v rozhozených řadách.
       1. nejprve docílíme toho, aby se všechny modré a zelené kostičky ocitli na pozici dvojice a žlutá i červená byly při tom každá ve svém pásmu (nikdy si nesmíme trvale rozhodit žluté a červené pásmo)
       2. toho docílíme následujícím postupem (vše se týká pouze 1. a pomocné řady):
          1. ať je kurzor kdekoliv, vždy smíme kurzorem otočit jedině tak, aby vzdálenost mezi pozicí žluté kostičky a pozicí žlutého pásma byla menší nebo rovna jedné
          2. typicky otáčíme kurzorem vpravo, je-li v 1. řadě, a vlevo, je-li v pomocné řadě
          3. máme-li žlutou kostičku vlevo od žlutého pásma, máme v 1. řadě 2 možnosti, co dělat. Buď otočíme o jednu nebo o dvě kostičky vpravo (oboje je v souladu s bodem i.).
          4. o 2 otočíme tehdy, je-li vlevo vedle žluté kostičky kostička bez barvy, o 1 tehdy, je-li tam kostička barevná (pochopitelně se zarazíme včas tehdy, platí-li I.)
       3. Nyní nastávají 4 možnosti:
          1. pakoválec je složen, pak není co řešit
          2. v obou řadách jsou prohozeny modrá a zelená
          3. nahoře nebo dole jsou dvojice modrá a zelená ve správných pásmech a na druhé straně je to prohozené
          4. v jedné řadě jsou obě modré v druhé obě zelené kostičky
       4. Nastane-li B, jsme téměř hotoví. Začneme dole(!) posunem kurzoru o jedno vlevo a opakujeme kroky podle II.ii. a to tak, že nikdy neotáčíme o 2. Časem nutně dojdeme ke složení.
       5. Nastane-li C, začneme kurzorem v dole(!), otočíme vpravo o 2, přemístíme nahoru, opět o 2 vpravo, přesuneme dolů, o 2 vlevo, nahoru a o 3 vlevo. Pokračujeme postupem podle bodu e.II.
       6. Nastane-li D, začněme kurzorem nahoře, otočíme o 1 vpravo, kurzor přemístíme dolů, o 1 vlevo, nahoru, o 2 vpravo, dolů, o 1 vlevo, nahoru, o 1 vpravo, dolů, o 1 vlevo, nahoru, o 1 vpravo, dolů, o 2 vlevo a nahoru. Dále pokračujeme postupem podle bodu e.II.
12. A je to složené!

Zajímavé řešení je uvedeno na Jaap stránkách.

Již během studií na MFF UK jsem si velmi oblíbil pravděpodobnost. Mohl za to především vynikající profesor prof. RNDr. Jaromír Antoch, CSc., který nás pravděpodobnost učil. Mezi moje 2 nejoblíbenější pravděpodobností úlohy patří Monty Hall Problem a Bertrand's box paradox.

Monty hall problem

Zadání:
Předpokládejme, že jste součástí hrací show, kde vám nabídnou možnost zvolit si jedny ze tří dveří: Za jedněmi je auto a za zbylými jsou kozy. Vy si vyberete tedy jedny dveře (řekněme číslo 1), které pro zatím zůstanou zavřené. Moderátor show, který ví, co se skrývá za kterými dveřmi, otevře jiné dveře (řekněme číslo 3), za kterými je koza. Poté se vás zeptá: "Chcete si vzít dveře číslo 2?" Otázka pro vás je, zda je ve vašem zájmu, abyste svoji původní volbu změnili?

K zadání ještě patří dodat, že moderátor otevírá vždy ty dveře, které obsahují kozu. Má-li moderátor volbu mezi dvěma dveřmi s kozou, vybírá dveře náhodně. Vaším cílem je pochopitelně získat auto :)

Nápověda:
Problém je velmi podobný, jako kdyby vám moderátor dal vybrat z 1000 dveří (1 auto + 999 koz) a otevřel 998 dveří s kozou (řekněme čísla 3,4,5, až 1000). Otázka zůstává stejná: "Chcete si vzít dveře číslo 2?"

Řešením pochopitelně je, že to je ve vaším zájmu, protože to zvýší vaší pravděpodobnost výhry z 1/3 na 2/3. Maximální, vyčerpávající a nejpřesnější informace najdete na Wikipedia, kde je celý problém krásně rozebrán a vysvětlen na obrázku (to už pak musí pochopit každý).

Bertrand's box paradox

Zadání:
Jsou 3 krabice: krabice obsahující 2 zlaté mince, krabice obsahující 2 stříbrné mince a krabice obsahující jednu stříbrnou a jednu zlatou. Náhodně si zvolíte krabici a náhodně z ní vytáhnete minci, řekněme že zlatou. Otázkou je, jaká je pravděpodobnost, že druhá mince v této krabici je také zlatá?

Řešením je pochopitelně 2/3 a nikoliv 1/2 jak by někoho mohlo napadnout. Člověk si musí uvědomit, že už krabici se dvěma stříbrnými mincemi neuvažuje a že měl celkem 3 možnosti, jak mohl zlatou minci vytáhnout: buď vytáhl minci z krabice, která obsahuje ještě stříbrnou minci (1 možnost), nebo vytáhl minci z krabice, kde byly 2 zlaté (2 možnosti). Odsud plyne, že pravděpodobnost je 2/3 (ve 2 případech ze 3 je druhá mince zlatá).

Podrobné informace má pochopitelně také Wikipedia.

Boy or Girl paradox

Zadání:
Nechť pohlaví každého narozeného dítěte je náhodné; nechť se s pravděpodobností 1/2 vždy narodí kluk a s pravděpodobností 1/2 vždy holka. Nechť pohlaví jednoho dítěte je vždy nezávislé na pohlaví druhého dítěte. Sledujeme náhodě vybrané rodiny, jejichž matka má právě 2 děti.
2 případy:
1) víme, že starší dítě je kluk. Jaká je pravděpodobnost, že to mladší dítě je taky kluk?
2) víme, že starší nebo mladší dítě je holka. Jaká je pravděpodobnost, že to druhé dítě je taky holka?

Řešením pochopitelně je 1) 1/2 a 2) 1/3. Člověk si musí uvědomit 1 důležitý fakt:
máme 4 možnosti kombinací pohlaví (nikoliv jen 3): K-K, H-K, K-H, H-H (K=kluk a H=holka).

Podrobné informace má pochopitelně také Wikipedia.