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. Az a) rész kérdésére a következő állítás fogja a választ szolgáltatni: bármelyik korongot megfordíthatjuk anélkül, hogy a többi színe megváltozna. Ebből ugyanis az következik, hogy tetszőleges helyzet elérhető, bármilyen elrendezésből induljunk is ki. Mivel , azért mindegyik korong mellett van ‐ valamelyik irányban ‐ legalább 94 korong. Fordítsuk meg a kiválasztott korongtól valamelyik oldalra levő 94 korongot, majd azt az -öt, amely a kiválasztottat és az előbb forgatott 94-et tartalmazza. Látható, hogy ezáltal csak annak az egynek változott meg a színe, s ezzel az állítást beláttuk. Lássuk, mi a helyzet a b) részt illetően. Mivel , elegendő csak a 19-es forgatásokat tekinteni: egy 95-ös ugyanis helyettesíthető öt szomszédos 19-es forgatással. Minden forgatás-sorozatot egy 1977 elemű 0‐1 sorozattal fogunk leírni, a következő módon: jelentse azt a forgatás-sorozatot, amelyben az -edik, -edik, , -adik korongokból álló 19-est páros sokszor forgattuk meg, ha , és páratlan sokszor, ha . Minthogy egy korong végső színét csak a forgatások számának paritása határozza meg, valamint a forgatások sorrendje is lényegtelen, ezért a megengedett forgatásokkal legfeljebb annyiféle elrendezés valósítható meg, mint az 1977 elemű 0‐1 sorozatok száma. Mivel ilyen sorozatból -féle van (hiszen mindegyik 0 vagy 1 lehet), azért egy tetszőleges helyzetből indulva ‐ mondjuk a csupa pirosból ‐ legfeljebb -féle helyzetbe juthatunk el. Korong-elrendezésből viszont -féle van: mindegyik korong vagy piros, vagy kék. Tehát van olyan elrendezés, amit nem kaphatunk meg, s mivel a forgatások visszafelé is elvégezhetők, azért egy ilyen állásból indulva nem kapható meg a csupa pirosból álló elrendezés. Megadunk azért egy konkrét felállást is, amiből nem érhetjük el a csupa pirosból álló helyzetet: legyen az utolsó korong kék, a többi piros. Tegyük fel, hogy ebből az állásból mégis elérhető a csupa piros sorozat. Nézzük meg, hogy hányszor fordítottuk meg az első korongot: azt csak az első 19 átforgatásával lehet mozdítani, s minthogy a színe nem változott, összesen páros sokszor lett átfordítva. Mivel a sorrend nem számít, és két megegyező egymás utáni forgatás minden korongot helybenhagy, azért feltehető, hogy ez a páros számú forgatás nullát jelent. Az első 19 korongot tehát nem fordítottuk meg, s a továbbiak szempontjából az elsőt el is hagyhatjuk. Ezután ugyanez elmondható a 2., 3., , 1997-edik korongról is, ami viszont azt jelenti, hogy az 1995-ödiket sem fordítottuk át, tehát a színe kék maradt, ami ellentmondás. Ezzel ismét beláttuk, hogy a b) rész esetén a válasz nemleges. (Ugyanezzel a gondolatmenettel az is belátható, hogy a megoldásban szerepelt megfeleltetés az elérhető elrendezések és az 1997 hosszúságú 0‐1 sorozatok között kölcsönösen egyértelmű, vagyis nemcsak legfeljebb, hanem pontosan -féle elrendezés állítható elő egy kiindulási helyzetből.) Hasonlóan kezelhető a következő, általánosabb eset is: ha legalább korong van, és , akkor bármilyen állást elérhetünk. Egyedül annyit kell még felhasználni, hogy az feltétel miatt léteznek olyan egész számok, amelyekkel áll, s ekkor darab -es és darab -es szomszédos forgatás fogja pontosan egy korong színét megcserélni. Ha pedig , akkor nem minden helyzet vihető át a csupa pirosba.
Terpai Tamás (Fazekas M. Főv. Gyak. Gimn., I. o.t.) és |
Hangya Balázs (Fazekas M. Főv. Gyak. Gimn., I. o.t.) dolgozata alapján |
|