Hanojská věž - mýty a matematika - The Tower of Hanoi – Myths and Maths

The Hanojská věž hádanka
A Hanojský graf

Hanojská věž - mýty a matematika je kniha v rekreační matematika, na Hanojská věž, baguenaudier a související hádanky. Napsal to Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović a Ciril Petr, a publikoval v roce 2013 Birkhäuser,[1][2][3][4][5][6][7][8] s rozšířeným druhým vydáním v roce 2018.[9] Výbor pro základní seznam knihoven Mathematical Association of America navrhl jeho začlenění do vysokoškolských knihoven matematiky.[2]

Témata

Ačkoli je tato kniha v rekreační matematika, bere svůj předmět vážně,[8] a přináší materiál z teorie automatů, výpočetní složitost, návrh a analýza algoritmy, teorie grafů, a teorie skupin,[3] topologie, fraktální geometrie, teorie chemických grafů, a dokonce psychologie[1] (kde související hádanky mají aplikace v psychologické testování ).[8]

1. vydání knihy mělo 10 kapitol a 2. vydání má 11. V obou případech začínají kapitolou nula, na pozadí a historii Hanojská věž puzzle, pokrývající jeho vynález v reálném světě Édouard Lucas a v bájném příběhu pro to vynalezl. První kapitola se zabývá Baguenaudier puzzle (nebo, jak se tomu často říká, čínské prsteny), vztahující se k věži Hanoj ​​jak ve struktuře státní prostor a ve skutečnosti, že to vyžaduje exponenciální počet tahů k vyřešení a pravděpodobně inspirace pro Lucase. Kapitola druhá představuje hlavní téma knihy, Hanojskou věž, v její klasické podobě, ve které je třeba přesouvat disky jeden po druhém mezi třemi věžemi a vždy udržovat disky na každé věži seřazené podle velikosti. Poskytuje několik různých algoritmy za vyřešení klasického hlavolamu (ve kterém disky začínají a končí všechny na jedné věži) co nejmenším počtem tahů a za shromažďování všech disků na jedné věži, když začínají v jiné konfiguraci, opět co nejrychleji. Zavádí Hanojské grafy popisuje stavový prostor skládačky a spojuje počet kroků skládačky se vzdálenostmi v tomto grafu. Po kapitole o „nepravidelných“ hlavolamech, ve které není seřazeno počáteční umístění disků na věžích, se ve čtvrté kapitole pojednává o „Sierpińských grafech“ odvozených z Sierpińského trojúhelník; ty úzce souvisí s hanojskými grafy se třemi věžemi, ale od nich se liší kvůli vyššímu počtu věží v Hanoji nebo vícerozměrných fraktálů Sierpinski.[4][7][9]

Následující čtyři kapitoly se týkají dalších variant Hanojské věže, ve kterých se používají více než tři věže, disky se mohou pohybovat pouze mezi některými věžemi nebo v omezených směrech mezi věžemi nebo pravidla, pro která lze disky umístěné, na kterých jsou upraveny nebo uvolněny.[4][9] Obzvláště důležitým případem je hlavolam Reve, ve kterém se pravidla nezmění, až na to, že místo tří jsou čtyři věže. Stará domněnka týkající se minimálního možného počtu tahů mezi dvěma státy se všemi disky na jedné věži byla nakonec prokázána v roce 2014, po vydání prvního vydání knihy, a druhé vydání obsahuje tento materiál.[7][10]

Některé definice a důkazy jsou rozšířeny do mnoha cvičení knihy.[7] Nová kapitola ve druhém vydání poskytuje tipy a dílčí řešení,[9] a poslední kapitola sbírá otevřené problémy a (ve druhém vydání) poskytuje aktualizace dříve uvedených problémů.[4][9] Kniha obsahuje mnoho barevných ilustrací a fotografií.[8]

Publikum

Knihu si mohou přečíst jak matematici zabývající se tématy týkajícími se věže hanoiské hádanky, tak i široké publikum se zájmem o rekreační matematiku. Recenzent László Kozma popisuje knihu jako základní čtení pro první typ publika a (navzdory občasné těžké notaci a encyklopedickým detailům) přístupné a zajímavé pro druhý typ, a to i pro čtenáře, kteří mají pouze matematické vzdělání.[4] Na druhou stranu recenzent Cory Palmer varuje, že „tato kniha není pro příležitostného čtenáře“ a dodává, že dobré porozumění kombinatorika je nutné si to přečíst,[6] a recenzent Charles Ashbacher naznačuje, že má dostatečnou hloubku obsahu, aby mohl být tématem pokročilého volitelného kurzu pro vysokoškoláky.[2]

I když je obecně pozitivní, recenzent S. V. Nagaraj si stěžuje na „významný počet chyb“ v knize.[5] Recenzent Andrew Percy tomu říká „příjemné dobrodružství“, „vtipné a velmi důkladné“.[7] Recenzent Martin Klazar knihu nazývá „báječnou“ a doporučuje ji všem zájemcům o rekreační matematiku nebo matematiku obecněji.[9]

Reference

  1. ^ A b Allouche, Jean-Paul (2014), "Recenze Hanojská věž - mýty a matematika (1. vyd.) " (PDF), Zpravodaj Evropské matematické společnosti, 93: 56
  2. ^ A b C Ashbacher, Charles (květen 2013), "Recenze Hanojská věž - mýty a matematika (1. vyd.) ", Recenze MAA, Mathematical Association of America
  3. ^ A b Bultheel, Adhemar (Únor 2013), "Recenze Hanojská věž - mýty a matematika (1. vyd.) ", Recenze EMS, Evropská matematická společnost
  4. ^ A b C d E Kozma, László (září 2014), "Recenze Hanojská věž - mýty a matematika (1. vyd.) " (PDF), Novinky SIGACT, 45 (3): 29–31, doi:10.1145/2670418.2670430
  5. ^ A b Nagaraj, S. V. (prosinec 2013), "Recenze Hanojská věž - mýty a matematika (1. vyd.) ", Recenze ACM Computing
  6. ^ A b Palmer, Cory (prosinec 2014), "Recenze Hanojská věž - mýty a matematika (1. vyd.) ", Matematický nadšenec, 11 (3): 753–754
  7. ^ A b C d E Percy, Andrew, "Recenze Hanojská věž - mýty a matematika (1. vyd.) ", zbMATH, Zbl  1285.00003
  8. ^ A b C d Sangwin, Chris (srpen 2015), „Review of Hanojská věž - mýty a matematika (1. vyd.) ", Matematický zpravodaj, 37 (4): 87–88, doi:10.1007 / s00283-015-9552-r
  9. ^ A b C d E F Klazar, Martin, "Recenze Hanojská věž - mýty a matematika (2. vydání) ", Matematické recenze, PAN  3791459
  10. ^ Z popisu vydavatele druhého vydání, jak je citováno Zbl  1387.00002

externí odkazy