Feladat: F.2219 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Beleznay Éva ,  Beleznay F. ,  Biczó Anikó ,  Bogdán A. ,  Bohus G. ,  Bozsó P. ,  Bölcsföldi L. ,  Csikós Zs. ,  Czakó F. ,  Dezsényi I. ,  Dosa Gy. ,  Feledi Gy. ,  Fodor L. ,  Gombás L. ,  Heckenast L. ,  Horváth 169 T. ,  Kappelmayer Hedvig ,  Kelemen B. ,  Keszei Zs. ,  Kiss 352 Gy. ,  Kovács 671 Ildikó ,  Kurusa Á. ,  Regős Enikő ,  Schwarcz Veronika ,  Simonyi G. ,  Sz. Nagy Cs. ,  Szegedy P. ,  Tóth V. ,  Tranta Beáta ,  Umann G. ,  Varga L. 
Füzet: 1980/március, 111 - 112. oldal  PDF file
Témakör(ök): Logikai feladatok, Teljes indukció módszere, Feladat
Hivatkozás(ok):Feladatok: 1979/október: F.2219

Egy tornaórán n gyerek áll egy sorban a tanárral szemben. Adott jelre mindegyikük 90-kal elfordul, néhányuk balra, mások jobbra. Ezután vezényszóra mindazok, akik valamelyik szomszédjukkal szemben állnak, hátra arcot csinálnak. Bizonyítsuk be, hogy az (n+1)-edik vezényszóra már senki sem mozdul meg.

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.

Tegyük fel, hogy akik a gyerekek közül jobbra fordultak, azok mind lányok voltak, a többiek fiúk. Legyen számukra is "előre'' az az irány, amerre a lányok néznek, és "hátra'' a fiuk iránya. Az első vezényszó előtt fogja meg minden olyan lány, aki előtt fiú áll, az előtte álló fiú kezét. Az első vezényszó hatására az egymás kezét fogó gyerekeknek kell hátra arcot csinálniuk. A bizonyítás érdekében módosítsuk a parancsot: cseréljenek helyet az egymás kezét fogó gyerekek. Ha csak a gyerekek állását vesszük figyelembe, ez a módosítás nem lényeges, hiszen így is ellenkezőre válik a szóban forgó helyeken az éppen ott tartózkodó gyerekek iránya.
A módosított feladatunk így szól: fiúk, lányok állnak libasorban, összesen n gyerek. A lányok előre néznek, a fiúk hátra. Vezényszóra minden olyan lány, aki előtt fiú áll, helyet cserél az előtte álló fiúval. Bizonyítandó, hogy az (n-1)-edik vezényszó után már nincs lány, aki előtt fiú állna.
Vegyük a sorban a k-adik lányt. k szerinti teljes indukcióval megmutatjuk, hogy a (k-1)-ediktől kezdve bármelyik vezényszó után már csak akkor állhat ez előtt a lány előtt egy másik lány, ha előttük a sorban már egy fiú sincs. Ha k=1, állításunk triviálisan igaz. Tegyük fel, hogy valamilyen k-ra már beláttuk az állítást. Legyen mondjuk a k-adik lány neve Klári, a (k+1)-ediké Sári. Indukciós feltevésünk szerint a k-adik vezényszótól kezdve Klári minden egyes vezényszóra helyet cserél egy fiúval mindaddig, amíg egyáltalán van előtte fiú a sorban. Jelöljük a k-adik vezényszó előtti helyzetben a Klári és Sári között álló fiúk számát m-mel. Ha m=0, és Klári előtt sem áll fiú sehol a sorban, készen vagyunk. Ha m=0, és Klári előtt van fiú a sorban, akkor közvetlenül előtte is fiú áll, akivel a k-adik vezényszó hatására helyet cserél. Ha tehát Sári előtt egyáltalán van fiú a sorban, akkor a k-adik vezényszó után biztosan lesz közte és Klári között is fiú. Az indukciós állítást ezzel beláttuk.
Az előbb bizonyított állítás segítségével a módosított állítást most már könnyen beláthatjuk. Ha ugyanis a k-adik vezényszó után a k-adik lány előtt még összesen f fiú áll, akkor azok újabb f vezényszó után elfogynak előle, ez a kislány tehát (k-1+f)<n vezényszó után már biztosan nem mozdul meg. Tehát már az n-edik vezényszóra sem mozdul meg senki.