Feladat: Gy.2398 Korcsoport: 16-17 Nehézségi fok: átlagos
Füzet: 1987/november, 391. oldal  PDF  |  MathML 
Témakör(ök): Kombinatorikai leszámolási problémák, Permutációk, Kombinatorika, Konstruktív megoldási módszer, Szöveges feladatok, Gyakorlat
Hivatkozás(ok):Feladatok: 1987/március: Gy.2398

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

A három gombot 3!= 6 különböző sorrendben nyomhatjuk le, a zár nyitásához így gombnyomásoknak egy olyan sorozatára van szükség, amelyik mind a hat lehetséges sorrendet tartalmazza. Megmutatjuk, hogy kilenc gombnyomás elegendő, ennél kevesebb viszont nem. Ha megszámozzuk az egyes gombokat az 1, 2, 3 számokkal, akkor az alábbi sorozat nyilván megfelelő: 123121321.
Tegyük fel, hogy van olyan, az 1, 2, 3 számokból készített nyolcelemű sorozat is, amely alkalmas a zár nyitására. Egy ilyen sorozat éppen hat próbálkozást tesz lehetővé ‐ így ennél rövidebb sorozat nyilván nem jöhet szóba ‐ tehát különböző pozíción kezdődő hármasok különbözők, és mindegyikük az {1,2,3} elemek egy-egy permutációja. Ebből az is következik, hogy szomszédos, vagy másodszomszédos elemek nem lehetnek egyenlők.
Tekintsük a harmadik helyen álló h elemet. Mivel két h-val kezdődő permutáció van, a h mégegyszer előfordul a sorozatban. Ez a második előfordulás nem lehet sem az első öt, sem pedig az utolsó két pozíción, különben volnának egymáshoz közeli egyenlő elemek, vagy pedig "nem férne el'' a másik h kezdetű permutáció. Így a h másodszor a hatodik pozíción fordul elő.
A két, h-val kezdődő permutáció ezután csak úgy lehet különböző, ha az ötödik és a hetedik helyen ugyanaz a szám áll. Ez viszont szintén nem lehetséges, hiszen így az ötödik helyen kezdődő hármasban az y elem megismétlődik. Valóban nem létezik tehát olyan nyolcelemű vagy rövidebb sorozat, amelyik biztosan nyitná a zárat.

 

h
 h
   h
   x
   y
   h
   y
   x