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 és tegyük föl, hogy az állítás minden olyan esetben igaz, amikor a katonák száma kisebb mint . 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ó katona egymáshoz viszonyított helyzete eredményezhet csak; azonban -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 -re is teljesül, tehát a szereplők számának minden értéke mellett igaz.
|
|