Všimnite si, že grafy na obrázkoch majú jednu zaujímavú vlastnosť: rovnakú dĺžku všetkých hrán. Otázka znie:
Existuje permutácia čísiel 1,2,...,n, kde n>6, ktorej graf má všetky hrany rovnakej dĺžky?
28 marca 2010
Ekvidištantné permutácie
Nech σ=(σ1,σ2,...,σn) je permutácia čísiel 1,2,...,n. Ak v rovine postupne spojíme body (σ1,σ2), (σ2,σ3),...,(σn-1,σn), (σn,σ1) a (σ1,σ2), dostaneme euklidovský graf, ktorý permutáciu σ plne charakterizuje. Na nasledovnom obrázku sú znázornené grafy permutácií (1,3,4,2) a (1,2,5,6,3,4).
Všimnite si, že grafy na obrázkoch majú jednu zaujímavú vlastnosť: rovnakú dĺžku všetkých hrán. Otázka znie:
Existuje permutácia čísiel 1,2,...,n, kde n>6, ktorej graf má všetky hrany rovnakej dĺžky?
Všimnite si, že grafy na obrázkoch majú jednu zaujímavú vlastnosť: rovnakú dĺžku všetkých hrán. Otázka znie:
Existuje permutácia čísiel 1,2,...,n, kde n>6, ktorej graf má všetky hrany rovnakej dĺžky?
Ale áno, bárskoľko -- pre každé N istého tvaru viem takú permutáciu nájsť. Daňou za to je, že až na jeden známy a jeden triviálny prípad sa v príslušnom grafe hrany pretínajú. Kryptická nápoveda by mohla byť, že stačí tancovať do kruhu v rytme krok-skok-skok-skok a zapisovať si kroky :-)
OdpovedaťOdstrániťPre iné N-ká poznám len jedno ďalšie riešenie (okrem jedného, ktoré už Rado napísal). Tam sa pre zmenu hrany nepretínajú, ale zatiaľ nevidím, ako ho zovšeobecniť a či sa to vôbec dá. V ňom pre zmenu behá po šachovnici splašený kôň, ktorý skáče v oboch smeroch o políčko ďalej, ako by mal :-)
goober: super. Počkáme si ešte pár dní na ďalšie komentáre.
OdpovedaťOdstrániťInak musím sa priznať, že sám som našiel len tie "zovšeobecniteľné" riešenia pre "n istého tvaru" a domnieval som sa, že pre žiadne iné n (okrem prípadu n=4 na obrázku) už riešenie neexistuje. Na toho splašeného koňa som sám zvedavý :)
Pokial by to niekoho zaujimalo, ten "splaseny" - predlzeny kon ma svoje meno. Napr. tie skoky z mriezky 6x6 su skokmi tavy. Viacere taketo sachove figury (presnejsie exofigury) maju zvieracie mena, niektore dalsie maju klasicke z arabstiny.
OdpovedaťOdstrániťHromadny pojem pre ne je skokan.
skokan(1,2) = jazdec
skokan(1,3) = tava
skokan(1,4) = zirafa
skokan(0,1) = vezir
skokan(1,1) = fers
skokan(0,2) = dababa
skokan(2,2) = alfil
skokan(2,3) = zebra
skokan(3,4) = antilopa
Inac, aj exosachisti prisli na to, ze niektore vzdialenosti sa vdaka Pytagorovej vete daju lahko vyjadrit inac a su dvaja skokani, ktori maju priamo v nazve sucet ploch stvorcov.
V25 skokan = skokan(0,5) + skokan(3,4)
V50 skokan = skokan(1,7) + skokan(5,5)
Priklady pozicii s takymito figurkami na francuzsko-anglickej stranke Problemesis.
Tu je to splašeno-konsko-zebrovité riešenie: (1, 4, 2, 5, 7, 10, 12, 9, 11, 8, 6, 3).
OdpovedaťOdstrániťMomentálne si myslím (ale dokázať zatiaľ neviem), že N=4 a N=12 sú jediné "špeciálne" prípady -- brute-force na počítači nenašiel nič, a to išiel pomerne ďaleko :-)
Inak, pár dní pred objavením sa tejto úlohy som si náhodou o neštandardných šachových figúrkach čítal... ale keď prišlo na písanie komentára, bol som lenivý pozrieť si, čo za zvera je ten skokan(2,3) :-)
Zaujimave, normalni ludia chodia po sibacke a goober tu pisu riesenia :) :)
OdpovedaťOdstrániťNuž, 6:50 ráno na veľkonočný pondelok je skutočne nezvyčajný čas na písanie komentárov k matematickým úlohám, ale každopádne gooberove riešenie je správne (a ja sám so ho neobjavil). Dovolil som si ho graficky načrtnúť tu.
OdpovedaťOdstrániťAko už bolo spomenuté, existuje aj celá séria odlišných riešení pre n=4k+2, kde k je prirodzené číslo. Príslušný obrázok pre n=14 nájdete tu a princíp si už ľahko zovšeobecníte.
Či existujú aj riešenia pre iné čísla n ako 2,4,12 a 4k+2, tak to jednoducho nevieme.
Tak, a už vieme :-)
OdpovedaťOdstrániťUzávierka Starého mostu a následná zmena objemu času stráveného v MHD pomohli vyprodukovať nasledovný (snáď aj správny) dôkaz, že iných riešení fakt nieto. Vznikalo to v rôznych časoch a opisom z rôznych kusov papierových poznámok... ale hádam to bude aspoň trocha konzistentné :-)
goober, prezrel som si to a vyzerá to byť dobre. Nebol by som býval povedal, že sa tento problém podarí niekomu vyčerpávajúco vyriešiť. Klobúk dole.
OdpovedaťOdstrániťMyslím si, že by bola škoda, ak by toto Tvoje riešenie malo zostať zapadnuté na QEDe. Mám opäť ďalší dôvod uvažovať o spísaní knihy z týchto problémov a Vašich (niekedy naozaj super) riešení.