25 februára 2009

Magická hviezda

Nemám už dnes síl seriózne pracovať a preto som sa rozhodol, že k rybám pridám ešte jednu matematickú úlohu úplne iného charakteru; na jej vyriešenie stačí vedieť sčitovať čísla od 1 do 12 :-). Mám ju z príjemnej a čerstvej knihy "Cabinet of Mathematical Curiosities" od známeho profesora z Warwicku Iana Stewarta.

Do krúžkov na obrázku doplňte čísla od 1 do 12 (každé z týchto dvanástich čísel je potrebné použiť práve raz), aby bol súčet každej štvorice čísel spojených úsečkou a taktiež šestice čísel na vonkajšej kružnici práve 26.

Poznámka 3.3.: V komentároch nájdete viaceré možné riešenia a iné zaujímavosti týkajúce sa tejto a podobných úloh.

16 komentárov:

rasťo povedal(a)...

Od Iana Stewarta sme kedysi doma mali peknú knižku o symetrii v prírode. Najnovšie sa mi ale jeho meno spája s esejou, ktorú napísal pre knižku The Next Fifty Years. Science in the First Half of the Twenty-First Century, ktorá vyšla v roku 2002. Pekne tam píše o vývoji a význame matematiky a odhaduje jej ďalšie smerovanie. Keď sa dostane k Hilbertovmu programu a k problémom, ktoré odolali 20. storočiu spomína aj ako na ne v roku 2000 vypísal Clayov matematický inštitút v Cambridgi (Massachusetts) odmenu po milióne dolárov. A potom sa pustí do robenia odhadov, ktoré problémy odolajú aj roku 2050, a ktoré nie. O Poincareho domnienke hádal, že odolá. Ja som čítal túto esej krátko predtým, ako sa strhol v médiách rozruch keď v roku 2006 Pereľman problém vyriešil, ale nechcel peniaze:-)

Odvtedy si vravím, že radšej nerobiť žiadne odhady o budúcnosti, alebo ich aspoň zapečatiť do obálky. A obálku odpečatiť iba ak sa predpoveď naplní. (To dokonca môžem na každú otázku spraviť dve navzájom opačné predpovede a potom otvárať len tie správne obálky... :-)

Radoslav Harman povedal(a)...

Čo sa týka tých predpovedí, pekne to vyjadril (údajne) Niels Bohr: "Prediction is very difficult, especially about the future."

Jedna z prvých kníh, ktorú som celú prečítal v angličtine, bola "Nature's Numbers" práve od Iana Stewarta; veľmi sa mi vtedy páčila. Inak "Cabinet of curiosities" je tiež veľmi pekná, problém je len v tom, že veľmi veľa v nej popísaných zaujímavostí som už poznal. Pre šikovného stredoškoláka so záujmom o matematiku však môže byť naozaj super.

rasťo povedal(a)...

Cez obed som sa snažil prísť na tú hviezdu, ale nevedel som to trafiť ani "systematicky uhádnuť", tak som si situáciu naprogramoval a vyšlo mi takéto riešenie.

Podobných hlavolamov s magickými štvorcami, sústrednými kružnicami a trojuholníkmi som už viedel veľa, ale nikdy mi nešlo do hlavy, či sú na to nejaké sofistikované finty, alebo treba len veľmi dlho skúšať. Keď však do svojej knihy takúto hádanku zaradil taký matematik, tak asi na to bude nejaká pekná metóda...?

Radoslav Harman povedal(a)...

rasťo: fajn! To riešenie je údajne jediné až na preklopenia a rotácie celej hviezdy.

Čo sa týka toho spôsobu hľadania, tak tiež som použil počítač (pre 12 čísiel je počet permutácií ešte relatívne malé číslo). Ale myslím, že by to šlo využitím série drobných postrehov a metódy pokusov-omylov aj "ručne", hoci Stewart ani len nenaznačil ako (len sucho uviedol riešenie a že je jediné až na preklopenie a rotácie).

Napríklad 1 musí byť na vonkajšom okruhu, pretože 2+3+...+7=27, čiže bez jednotky by si iba 26 na vonkajšom okruhu nevyrobil. Podobne 12 musí byť vo vnútornom okruhu, lebo 12+1+2+..+5=27, čiže ak by bola 12 na vonkajšom okruhu, opäť by si na ňom nevyrobil iba 27. Verím tomu, že podobných postrehov sa dá nájsť viac a v kombinácii s trochou dávky šťastia by človek dané riešenie našiel aj bez počítača.

Samozrejme ak niekto nájde systematický postup ako sa k riešeniu dopracovať bez počítača, budem veľmi rád, keď nám ho napíše.

Anonymný povedal(a)...

Tiez poznam dost vela podobnych uloh (patria sem napriklad aj magicke stvorce, daju sanamiesto ciesle 1,2,3.. dosadzat prvocisla atd.). Vela peknych sa ich da najst v ruskom casopise Kvant, ktory okrem ineho obsahuje jednu stranku uloh, pre mladsich, zacinajucich matematikov.
Vacsinou sa tieto ulohy riesia presne tak, ako uz bolo pisane. Vsimne sa zopar veci ktore musia platit a potom sa to doskusa dokonca. Jedna vcelku pekna uvaha zvacsa byva takato: ked nieje zadany sucet jednotlivych casti (v nasom pripade to bolo 26), ale len ktore cisla treba doplnit a ktore casti davaju ROVNAKY sucet, tak sa da tento sucet casti zistit. Ide to z celkoveho suctu cisel a z toho kolkokrat sa ktore "miesto pre cislo" na doplnenie pouzije... Takze vieme dostat napr. ze sucet vsetkych cisel je rovny piatim suctom casti. A z toho aj sucet jednej casti.

Radoslav Harman povedal(a)...

Ja by som ešte dodal, že na wikipedii je rozsiahly článok o magických štvorcoch. Najviac ma zaujalo to, že na ich hľadanie sa dá pomerne efektívne použiť genetický algoritmus.

joshu povedal(a)...

je aj toto iba nejake preklopenie ci rotacia?

Radoslav Harman povedal(a)...

Jozef: Ejha! Zdá sa, že sa potvrdilo príslovie, že aj majster tesár sa utne. Citujem zo Stewartovej knihy, strana 271:

"This arrangement - possibly rotated or reflected - is the only solution."

A uvádza tento obrázok.

A to sú pritom všetky tri očíslovania (rasťove, Jozefove a Stewartove) navzájom neizomorfné, t.j. ani jedno sa nedá na žiadne iné previesť len sériou rotácií a preklopení. (To očíslovanie, ktoré som si našiel ja, bolo zhodou okolností izomorfné Stewartovmu a potom som ho už s tým Rasťovym neporovnával.)

Možno by sme mali napísať priamo Stewartovi. Chýb som v tej knihe našiel viac, ale táto je dosť závažná; nie len nejaký preklep.

Radoslav Harman povedal(a)...

Tak pustil som svoj programík trochu dlhšie. Našiel mi všetky tri dosiaľ uvedené riešenia a k tomu ešte ďalšie tri. Všetkých šesť je pritom rôznych v tom zmysle, že žiadne z nich sa nedá previesť na žiadne iné len preklopením, alebo rotáciou.

Môj programík je to najjednoduchšie čo sa dá napísať, totiž náhodné generovanie obrovského množstva permutácií čísiel 1:12 a pri každej z nich overenie všetkých 7 požadovaných rovností (Tých náhodných permutácií som testoval asi 100 miliónov). Nie je teda vylúčené, že existuje aj nejaké ďalšie neizomorfné riešenie, ale nepredpokladám, lebo po krátkom čase mi už môj program hádzal výlučne také riešenia, ktoré už našiel predtým.

Každopádne Stewart sa s tou jednoznačnosťou riešenia dosť sekol.

rasťo povedal(a)...

To je vtipné. Hanbil som sa napísať, že som bol lenivý, a preto môj program testoval náhodné 12tice a nie systematicky všetky permutácie:-)

Inak, na magické štvorce je expert docent Solčan, treba sa ho niekedy spýtať, či sú na to nejaké triky, možno by vedel niečo aj o tejto hviezde.

Radoslav Harman povedal(a)...

rasťo: To nie je lenivosť, ale rozumné šetrenie časom :-).

Myslím to vážne. Ak by som mal programovať systematické generovanie všetkých permutácií, minul by som 20 minút práce. Ak však existuje aspoň jedno riešenie (čo sa dá čakať zo zadania), existuje ich aspoň 12, takže pravdepodobnosť náhodného trafenia riešenia je minimálne 1/11!. Pri rýchlosti tak 50000 testov náhodného očíslovania za sekundu (v R-ku) je stredná doba čakania na prvé riešenie 11!/50000, čo je zhruba 800 sekúnd. Skrátka pri tomto jednoduchom Monte-Carlo prístupe získa človek s veľkou pravdepodobnosťou riešenie s menšou námahou a rýchlejšie ako je systematické prehľadávanie.

Unknown povedal(a)...

Viacere jazyky maju na nasledujucu permutaciu priamo funkciu (napr. v C++ je next_permutation), takze tolko prace navyse to zase nemusi byt, ked sa pouzije spravny nastroj ;)
Druhy faktor je rychlost, mojmu programu v C++ stacilo nejakych 5 sekund na prezretie vsetkych zaujimavych permutacii.
A rieseni je naozaj len 6, nijake ine to nenaslo.

Radoslav Harman povedal(a)...

misof: Ďakujem(e), že si skontroloval, či sú tie riešenia všetky.

Čo sa týka tej rýchlosti; samozrejme, že skompilovaný program v C++ sú iné fukoty ako interpretovaný skript v R-ku. Ak si ešte využil napríklad tie jednoduché pozorovania, ktoré som popísal vyššie, t.j. že stačí na fixné miesto na vonkajšej kružnici dať jednotku a pre dvanástku sú vzhľadom k tej jednotke v zásade len 3 rôzne pozície na vnútornej kružnici, tak tých 5 sekúnd absolútne verím.

Možno naozaj napíšem krátky mailík Stewartovi.

Radoslav Harman povedal(a)...

Len pre zaujímavosť: Napísal som o našom "objave" Stewartovi a on mi odpísal, že konkrétne o tejto chybe už vedia. Zároveň mi poslal errata, kde je popísaných najakých 10 ďalších chýb a nedostatkov; tie som si prešiel a hneď som mu napísal ešte o jednej chybe, ktorú som pri čítaní objavil, ale v zozname ju nemali. Možno som máličko prispel ku kvalite ďalších printings, ktoré sa kvôli popularite tejto knihy chystajú. :-)

rasťo povedal(a)...

Fíha, tak to je super! Ja som mal pochybnosti, či vôbec nejako zareaguje, a on takto promptne odpísal? Tak to je skvelé, to sa mi páči :-)

Radoslav Harman povedal(a)...

Ja mám skúsenosti, že takýto ľudia sú celkom normálni a príjemní. Netreba sa príliš hanbiť s nimi komunikovať, ale tiež by nebolo dobré ich obťažovať príliš. Na tri riadky som mu stručne a jasne vysvetlil o čo ide a on mi slušne poďakoval (a podpísal sa Ian, čo dobre padne :). Viac ho už nejdem otravovať; musel by som mať na to naozaj vážny dôvod.