Feladat:	B.4302	Korcsoport: 16-17	Nehézségi fok: átlagos
Megoldó(k):	Beke Lilla
Füzet:	2012/szeptember, 349. oldal		PDF  |  MathML
Témakör(ök):	Feladat, Logikai feladatok, Indirekt bizonyítási mód
Hivatkozás(ok):	Feladatok: 2010/november: B.4302

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.   Megoldás. Az állítást a katonák számára vonatkozó indukcióval látjuk be; ha ez a szám 1 vagy 2, akkor az állítás nyilván teljesül (legfeljebb egy fordulás történhet). Legyen a sorban állók száma $n>2$ és tegyük föl, hogy az állítás minden olyan esetben igaz, amikor a katonák száma kisebb mint $n$. Indirekt bizonyítunk: feltesszük, hogy a forgolódás sohasem ér véget, vagyis lesz olyan katona, aki végtelen sokszor fordul meg. A sor két végén állók nem lehetnek ilyenek, hiszen ők legfeljebb egy-egy elfordulást követően ,,kifelé'' néznek, így nem kerülhetnek szembe a szomszédjukkal, ezért a továbbiakban mozdulatlanok. Ezután viszont minden további mozgást a fennmaradó $n-2$ katona egymáshoz viszonyított helyzete eredményezhet csak; azonban $n-2<n$-re az indukciós feltevés szerint véges sok ,,lépésben'' megáll a folyamat, ami ellentmond indirekt feltevésünknek. A kapott ellentmondás igazolja, hogy az állítás $n$-re is teljesül, tehát a szereplők számának minden értéke mellett igaz.