Feladat: Gy.3009 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Bárány Kristóf ,  Barát Anna ,  Gueth Krisztián ,  Győri Nikolett ,  Hangya Balázs ,  Horváth Gábor ,  Juhász András ,  Katona Zsolt ,  Kormos Márton ,  Lippner Gábor ,  Molnár-Sáska Balázs ,  Németh András ,  Nyul Gábor ,  Pap Júlia ,  Reviczky Ágnes ,  Salamon Éva ,  Szabó Anett ,  Szabó Gábor ,  Szalai-Dobos András ,  Szűcs Gábor ,  Terpai Tamás ,  Tóth Ádám ,  Végh László ,  Zawadowski Ádám ,  Zubcsek Péter Pál 
Füzet: 1996/április, 207 - 208. oldal  PDF file
Témakör(ök): Egyéb feladványok, Algoritmikus eljárások, Ellenpélda, mint megoldási módszer a matematikában, Indirekt bizonyítási mód, Gyakorlat
Hivatkozás(ok):Feladatok: 1995/október: Gy.3009

Az asztalon 1995 korong fekszik egymás mellett egy sorban. A korongok egyik oldala piros, másik oldala kék. Egy lépés során megfordíthatunk m vagy n szomszédos korongot. Igaz-e, hogy bármilyen helyzetből is indulunk, elérhetjük azt, hogy mindegyik korong piros oldala legyen fölfelé, ha
a) m=19 és n=94
b) m=19 és n=95?

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 1995-12>94, 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 5×19=95-ö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 95=519, 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: (a1,a2,...,a1977) jelentse azt a forgatás-sorozatot, amelyben az i-edik, (i+1)-edik, ..., (i+18)-adik korongokból álló 19-est páros sokszor forgattuk meg, ha ai=0, és páratlan sokszor, ha ai=1. 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 21977-féle van (hiszen mindegyik ai 0 vagy 1 lehet), azért egy tetszőleges helyzetből indulva ‐ mondjuk a csupa pirosból ‐ legfeljebb 21977-féle helyzetbe juthatunk el. Korong-elrendezésből viszont 21995-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 21977-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 2max(m,n) korong van, és (m,n)=1, akkor bármilyen állást elérhetünk. Egyedül annyit kell még felhasználni, hogy az (m,n)=1 feltétel miatt léteznek olyan egész számok, amelyekkel am+bn=1 áll, s ekkor a darab m-es és b darab n-es szomszédos forgatás fogja pontosan egy korong színét megcserélni. Ha pedig (m,n)1, 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