Baguenaudier játék

A baguenaudier vagy baguenodier (etimológiailag "gyűrűs csomó"; angolul Chinese Rings , Cardan's Függesztés , Cardano's Rings , Ördög tűje vagy öt oszlopos puzzle) egy mechanikus rejtvény , amely egy zárt hurokot képező (esetleg rugalmas) mobil merevlemezből és merev gyűrűkből áll. (mozgatható, ha a shuttle merev), mindegyiket ugyanazon tartóra kapcsolt rúd tartja.

Ezt a játékot John Wallis és Jérôme Cardan tanulmányozta műveiben .

A játék kínai eredetű lehet.

Matematikai megoldás

Édouard Lucas , a hanoi tornyok feltalálója megoldást javasolt a bináris rendszer és Gray rejtvényeként megfogalmazott kódja alapján . A minimális számú elmozdulások, hogy megoldja a gyűrű problémát adott alábbiakban (hivatkozott A000975 a OEIS-ben ): $nem$

a (n) = \ lceil \ tfrac {2 ^ {n + 1} -2} {3} \ rceil = \ elején {esetek} \ frac {2 ^ {n + 1} -2} {3}, és \ szöveg {amikor} n \ text {páros,} \\ \ frac {2 ^ {n + 1} -1} {3}, és \ text {amikor} n \ text {páratlan.} \ end {esetek}

hol van a felesleges teljes része (mennyezete) . $\ lceil x \ rceil$ $x$

Algoritmikus változat

Vegyük fontolóra a játék bináris reprezentációját: A játék megoldása azt jelenti, hogy az összes mezőt 1-re állítjuk (vagy fordítva, mindet 0-ra állítjuk).

Fizikai baguenauderrel a dobozok "kitöltése" vagy "ürítése" abból áll, hogy egy fő karikát vagy zsinórt (a megfelelő sorrendben) áthelyeznek a játék egyik kis gyűrűjébe vagy oda, hogy a zsinór vagy a karika fő elengedhető legyen. az összes kicsi gyűrű közül, fordítva, vagy zárja be a zsinórt vagy a karikát az összes kicsi gyűrű mellett: a "dobozok" az egyes kicsi gyűrűk állapotát jelentik (vagyis ha a nagy karika vagy a zsinór áthalad vagy nem mindegyiken) kis gyűrű).

A rugalmas zsinórral való játék azonban egyszerűbb kezelést igényel az egyik állapotról a másikra váltáshoz; A hajlíthatatlan karikával való játékhoz nagyobb ügyességre van szükség ahhoz, hogy a kis gyűrűk áthaladjanak egymáson, még akkor is, ha a karika áthalad a középpontjukon vagy sem (amelyek akkor különböző átmérőjűek vagy rugalmasan deformálhatók, vagy pedig hajlíthatatlanok, de ovális alakúak, amelyekhez ezután szükség van hogy forgatásukat pontosan ellenőrizzék, különösen akkor, ha az oválisok nagyon kissé lapítottak, és csak az szükséges, hogy az egyik kis gyűrű átkerülhessen a másikba).

A baguenaudier kínai változatában a kezelési nehézséget növeli az a tény, hogy a kis gyűrűk mindegyike rugalmatlan és azonos méretű (akárcsak a karika), de a kis gyűrűket mindegyik horog tartja (amely elfordulhat) szabadon) egy rövid, hajlíthatatlan rúd végén, a rudakat (mindegyik azonos hosszúságú) párhuzamosan tartják a szabályos távolsággal egy rugalmatlan tartóban, de képesek hosszirányban átcsúszni ezen a támaszon: a gyűrűk tájolása helyett mozogjon előre vagy hátra úgy, hogy becsúsztatja a támasztórudat, ahová az egyes gyűrűk kapcsolódnak, majd a gyűrűk forgatását a kampó helyzetébe hajthatja végre. Ez az elrendezés zavaró a játék kísérletezője számára, aki nem érzékeli jól, hogy a probléma valójában miért egyszerűbb, mint amilyennek látszik, de nagy ügyességet igényel a megoldás, mert a gyűrűk (amelyek nagyon szabadon forognak körül horgukat), és állítsuk be a rudak csúszását (ami szintén ingyenes): ezt a problémát nem lehet megoldani, ha a rudak nem vízszintesek (úgy, hogy a gravitáció miatt önmagukban nem csúsznak el a tartóban, ami szintén az egyes gyűrűk átirányítása, de nem a kezelő által kívánt módon).

De egy kísérletező számára, aki ismeri a manipuláció technikáját, a baguenaudier rugalmatlan verziója sokkal gyorsabb manipulációt tesz lehetővé (legalább egy változtatást vagy "löketet" másodpercenként), mint egy rugalmas transzferrel (vagy minden változtatás több másodpercig is eltarthat, miközben vigyázzon arra, hogy a transzfer rugalmas hurkai ne maradjanak meg az egyes gyűrűkben, de a transzfer hajlításának rugalmassága megváltoztathatja a helyét, ha a manipulátor nem tartja meg a szélső hurokokat, miközben elegendő hosszirányú feszültséget tart az ingán Ez az egyik, de gyakran ez a transzfer a szükségesnél hosszabb és nem marad feszült, ezért az egyik hurok könnyen szabadon kijuthat a gyűrűből, ahová a manipulátor elhelyezte).

De algoritmikusan ezeken a fizikai baguenaudiereken megoldandó problémák (amelyeknek sok változata van a világon, néhány évezredig több évezred) egyenértékűek a bináris "dobozok" matematikai problémájával (amely nem igényel semmilyen kézügyességet, de csak a logikus gondolkodás).

Szabályok

Az 1. mezőt mindig megfordíthatja (1-ről 0-ra vagy fordítva).
Nem tudjuk megfordítani ("üres" vagy "kérni") a mezőt , amely: j{\ displaystyle j} $j$ j∈[2,nem]{\ displaystyle j \ itt: [2, n]} ${\ displaystyle j \ itt: [2, n]}$
- ha a cella 1-nél van, és az összes előző cella 0-n van, vagy ${\ displaystyle j-1}$
- ha a cella 0-on van, és az összes előző cella 1-nél van. ${\ displaystyle j-1}$

Ezek a szabályok teljesen szimmetrikusak, ellenkező irányú megoldást kapunk, ha az 1. és a 0. értéket egyszerre fordítjuk meg az összes mezőben. Ez egyenértékű megoldást ad az ellentétes problémára is (a zsinór vagy a karika felszabadítása a kis gyűrűkből, vagy az összes kis gyűrű áthaladása).

Ugyanígy a pusztán bináris probléma a dobozok előre létrehozott, de összességében tetszőleges számozását (sorrendjét) használja (a dobozokat mindig be lehet permetezni). A fizikai játék viszont előír egy rendet, amelyet a konstrukciója szab meg, de ez a sorrend nem okoz nehézséget a probléma algoritmikus megoldásának, amely megoldást nyújt a kezdetektől elrendelt sorrendtől függetlenül.

Megoldás $n = 4$

Legalább 10 lépés (és kevesebb, mint 10 másodperc) szükséges a baguenaudier megoldásához . Minden 2 lépés, az 1. doboz megfordul, minden 4 lépés a második mező megfordul, az utolsó félidőben lévő dobozok mindegyike csak egyszer fordul meg külön mozdulatokban (4 mozdulattal egymástól). Számos megoldás lehetséges (kombinatorikus módon a probléma szimmetriája és a dobozok tetszőleges kezdő sorrendje miatt), ezért 10 lépésben minimális megoldások vannak, amelyek közül itt egy van (ami az inverz probléma megoldását is jelenti) , balról jobbra vagy jobbról balra olvasva, vagy alternatív megoldásként az egyes dobozok 1 vagy 0 állapotainak értelmezését permutálva; ha ezt a két értelmezési változást egyidejűleg hajtjuk végre, akkor ugyanannak a második megoldását is kapjuk kezdeti probléma, mert ez egyszerűen megfordítja a dobozok sorrendjét, és így a 24 lehetséges permutációból egy másik adódik). : $n = 4$ ${\ displaystyle n! = 24}$

1. eset:	1		1	⬌	0		0	⬌	1		1	⬌	0		0	⬌	1		1	⬌
2. eset:	1	⬌	0		0		0		0	⬌	1		1		1		1	⬌	0
3. eset:	1		1		1		1		1		1		1	⬌	0		0		0
4. rovat:	1		1		1	⬌	0		0		0		0		0		0		0

A baguenaudiereket hagyományosan páratlan számú gyűrűvel építik: az 5 gyűrűvel rendelkező leggyakoribb modellek 21 löketet igényelnek (és ezért rugalmatlan alkatrészekkel kevesebb, mint 20 másodperc alatt könnyen kinyithatók és bezárhatók). Léteznek 7 gyűrűvel rendelkező modellek, amelyek minimum 85 löketet igényelnek, ezért valamivel több mint egy percet kell nyitniuk vagy bezárniuk legalább löketekkel. A merev 9 gyűrűs modellhez legalább 341 löket szükséges, ezért csaknem 6 perc folyamatos kezelés (legalább egy löket másodpercenként), hogy teljesen hiba nélkül kinyíljon vagy bezáruljon.

Algoritmus

Az (n) kitisztítással a baguenaudier n doboza 1-ről 0-ra mozog, az (n) kitöltésével a baguenaudier n doboza 0-ról 1-re áll. Az (i) elhelyezésével az i doboz egyenlő 1-vel, eltávolítva az (i) az i esetet 0-val egyenlővé teszi.

def remplir(n) : if n == 1 : poser(1) elif n > 1 : remplir(n-1) vider(n-2) poser(n) remplir(n-2) def vider(n) : if n == 1 : enlever(1) elif n > 1 : vider(n-2) enlever(n) remplir(n-2) vider(n-1)

Biztonság

A bináris baguenaudier egykor egy elemi ál- zár francia parasztok. Ez azonban nem jelenthet valódi biztonságot, mert az objektum állapotától függetlenül (kivéve, ha teljesen zárt vagy teljesen nyitott), csak két irányban lehet manipulálni: a játék teljes grafikonja egyetlen szegmensre redukálódik, amely csatlakozik a teljes nyitás és a teljes bezárás állapota. Ha megértettük, hogyan kell kezelni az objektumot, és még akkor is, ha nem tudjuk, hogy melyik irányba kezdjük el, választhatunk a kettő közül egyet, és elvégezhetjük a manipulációkat anélkül, hogy valaha is visszamennénk, és bármelyik helyzetbe kerülünk, az objektum teljesen nyitva van, vagy ahol teljesen zárva van; ha nem ezt a helyzetet akarjuk megszerezni, elegendő az ellenkező irányú műveletek folytatása a kívánt végső állapot eléréséhez. Az egyetlen elért biztonság (mivel biztosak vagyunk benne, hogy könnyen találunk megoldást) az az idő, amely egy ilyen zár kinyitásához szükséges, ezúttal csak a gyűrűk számától függ.

Más komplexebb, átlapoláson alapuló játékok léteznek, amelyek algoritmikus felbontása a nem bináris logikának engedelmeskedik: ekkor sokkal bonyolultabb az egyes mozdulatoknál a különböző lehetséges lehetőségek feltárása. Például egyetlen transzfer helyett csak annyit kell tennie, hogy hozzáad legalább egy másodikat, amely összefonódik a gyűrűkkel és a másik transzferrel is. Ezért minden lépésnél meg kell határoznunk, hogy melyik transzfert kezeljük (ezt a játékot "csomózsáknak" is nevezhetjük, ez általában a kábelek tárolásának ismert problémájában található meg, amelyet különösen nehéz kibogozni, ha összekapcsolódnak egy az elővigyázatosság nélkül kezelt konténer), és a játék mindig felderítetlen lehetőségeket kínál, vagy nem könnyű meghatározni, ahogyan azt már feltártuk (mert az átlapolás elfedi belső állapotainak egy részét, amelyhez a manipulátornak nincs hozzáférése, vagy amelyhez bezárását okozta anélkül, hogy tudta volna). Vannak azonban nem bináris logikai interlea játékok, amelyek olyan részeket használnak, amelyek állapota nincs elrejtve a felhasználó elől, és minden lépésnél mindig kettőnél több lehetséges lépést kínálnak: ezek megoldásához a felhasználónak fel kell szólítania a memóriájában, hogy emlékezzen a már kombinációkra feltárva, de számuk kombinatorikus vagy exponenciális módon gyorsan felrobban, ezt a játékot aztán nagyon nehéz vagy akár lehetetlen megoldani egy ember, aki akkor még nem tudja, hogy jó úton jár-e a kívánt megoldás felé. Másrészt, ha a felhasználó ismeri vagy megvan a kombináció (a kulcs), amely a nyitáshoz vezet, akkor gyorsan elvégezhet egy előre meghatározott és korlátozott számú lépést, és könnyen megtalálja a megoldást (kinyithatja vagy bezárhatja a zárat) anélkül, hogy sokat veszítene idő. idő (ami nem a klasszikus baguenaudier esetében van).

Az ilyen játékok grafikonja nem egy vonalat, hanem sok ágú orientált fákat képez, esetleg végtelen belső hurokkal (ami észrevehetetlen lehet, ha a játék szándékosan elrejti belső állapotainak egy részét egy fekete dobozban lévő játékos elől, és csak a játékossal lép kölcsönhatásba. mint szándékosan korlátozott válaszokat adó „orákulum”). Az ilyen készletek felhasználhatók valódi biztonsági eszközök létrehozására (és ezért " zárakként " használhatók : pontosan vannak olyanok, amelyek a fogazott kerekek, a visszavezető rugók és a reteszelő rovátkák összetett belső összeállításán alapulnak, amelyek az egyszerű váltót helyettesítik, ahol bármilyen kezelési hiba arra kényszerít, hogy kezdettől fogva folytassa a kezelést teljesen zárt állapotban, a visszakövetést a berendezés blokkolja annak érdekében, hogy jelentősen lelassítsa a lehetőségek szisztematikus feltárását; további nehézséget jelent, hogy még az a felhasználó is, aki nem ismeri a helyes nyitást nem tudja, hogy a berendezés mikor tér vissza automatikusan a teljes zárási konfigurációba, mert ugyanazok a belső mechanikai mozgások a helyes nyitási sorrend részét képezik).

Az ilyen komplex játékok modernizált (és matematikailag modellezett) változata a számítástechnika által használt titkosítási algoritmusokból áll (például az egész számok főtényezőkké történő bontása alapján), valamint a nem bináris aritmetikai kombinatorika alapján (ahol minden lépésnél ott van) több mint két lehetséges lépés, és ahol nem könnyű meghatározni, melyik vezet a kívánt megoldáshoz, anélkül, hogy minden lehetséges utat fel kellene tárnunk, sok kudarc esetén a visszalépés vagy a kezdetektől való folytatás).

Bibliográfia

Luc-Agathon-Louis Gros , baguenodier elmélete, a lyoni lyoni jegyző ügyintézője , Aimé Vingtrinier ,1872( online olvasás )
Édouard Lucas , Matematikai kikapcsolódás , vol. 1, Párizs, Gauthier-Villars ,1882, " Hetedik kikapcsolódás: A baguenaudier játék ", p. 161–186
Auguste Héraud , Tudományos játékok és rekreáció: A matematika, a fizika, a kémia és a természettudomány egyszerű alkalmazásai , Párizs, Jean-Baptiste Baillière et fils ,1884, fej. XVI (" Matematikai játékok és szerencsejátékok: Baguenaudier játék "), p. 604-609

Hivatkozások

Lucas 1882 , p. 177. [ online olvasás ] .
Héraud 1884 , p. 604 [ online olvasás ] .
Gros 1872 , " Wallis algebra ", p. 8–11.
Gros 1872 , "A kardán finomsága ", p. 5–8.
(in) David Darling , " kínai gyűrűk " , Encyclopedia of Science on The Worlds David Darling .
(in) Eric W. Weisstein , " Baguenaudier " a MathWorld- on .