Feladat: N.89 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Balogh Bálint ,  Barta Ágnes ,  Braun Gábor ,  Csillag Zita ,  Frenkel Péter ,  Gyarmati Katalin ,  Gyenes Zoltán ,  Katona Borbála ,  Kőműves Balázs ,  Koncz Imre ,  Kutalik Zoltán ,  Léka Zoltán ,  Lukács László ,  Makai Márton ,  Megyeri Csaba ,  Naszvadi Péter ,  Pál András ,  Pap Gyula ,  Pap Júlia ,  Szita István ,  Terék Zsolt ,  Terpai Tamás ,  Vörös Zoltán ,  Zubcsek Péter Pál 
Füzet: 1996/december, 542 - 543. oldal  PDF file
Témakör(ök): Logikai feladatok, Algoritmikus eljárások, Nehéz feladat
Hivatkozás(ok):Feladatok: 1996/január: N.89

Nevezzük betűk véges hosszúságú sorozatát szónak. Egy szóval a következő műveleteket végezhetjük:

a) Elhagyjuk az első vagy az utolsó betűjét;

b) A szót ,,megduplázzuk'', azaz a szó két példányát egymás után írjuk.

Eljuthatunk-e ilyen lépésekkel az ABCD...XYZ szótól a ZYX...DCBA szóhoz?

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.

Legyen α egy tetszőleges szó, x az α egy betűje. Az αα szó (α kétszeri leírásával kapott szó) elejéről hagyjuk el a betűket mindaddig, amíg egy x betűhöz nem érünk. Így egy xγα alakú szót állítottunk elő (γ akár az üres szó is lehet). Az xγαxγα szó elejéről, illetve végéről elhagyva a megfelelő betűket, az αx szóhoz juthatunk el a megengedett lépésekkel.
Legyen most β egy olyan szó, amely csak α betűiből áll. A fent elmondottak alapján β betűit a megfelelő sorrendben kimásolva α végére az αβ szót kapjuk. Ennek a szónak az elejéről elhagyva α-t, a β szóhoz jutunk el.
Tehát beláttuk, hogy α-ból a megengedett lépésekkel minden olyan szóhoz eljuthatunk, amely csak α betűit tartalmazza (más szavakhoz pedig nyilván nem juthatunk el). Speciálisan, az ABCD...XYZ szóból eljuthatunk a ZYX...DCBA szóhoz.

 Braun Gábor (Budapest, Szent István Gimn., III. o.t.) dolgozata alapján