Feladat: Gy.2951 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Bárány Kristóf ,  Csordás Péter ,  Deli Tamás ,  Devecsery András ,  Erdélyi Tibor ,  Fazekas Borbála ,  Formanek Csaba ,  Füredi Zoltán ,  Gyurkó L. Gergely ,  Gönczi Orsolya ,  Hangya Balázs ,  Harmati Péter ,  Jenei Piroska ,  Jeszenszky Gyula ,  Juhász András ,  Kántor László ,  Katona Zsolt ,  Kiss Gergely ,  Kiss László ,  Laczó Tibor ,  Lippner Gábor ,  Major Csaba ,  Mátrai Tamás ,  Méder Áron ,  Megyeri Csaba ,  Molnár-Sáska Balázs ,  Opor Károly ,  Pap Gyula ,  Pápai Tivadar ,  Pintér Dömötör ,  Pogány Ádám ,  Puskás Péter ,  Reviczky Ágnes ,  Rudolf Gábor ,  Sragner László ,  Szabó Gergely ,  Szilágyi Zoltán ,  Varga Balázs ,  Varga Péter ,  Zubcsek Péter Pál 
Füzet: 1995/április, 218 - 219. oldal  PDF file
Témakör(ök): Teljes indukció módszere, Algoritmikus eljárások, Gyakorlat
Hivatkozás(ok):Feladatok: 1994/december: Gy.2951

Egy n×n-es táblázatban megjelöltünk n-1 mezőt. Egy lépés során felcserélhetünk két sort vagy két oszlopot. Igazoljuk, hogy ilyen lépésekkel elérhetjük, hogy az összes megjelölt mező a főátló alatt legyen. (A főátló a táblázat bal fölső és jobb alsó sarkát köti össze.)

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.

Teljes indukcióval be fogjuk látni, hogy ha egy n×n-es táblázatban legfeljebb n-1 megjelölt mező van, akkor a sorok és oszlopok cserélgetésével elérhető a kívánt állapot.
Ha n=1, akkor az állítás triviális, mert nincs megjelölt mező.
Tegyük fel, hogy n=(k-1)-re igaz az állítás. Megmutatjuk, hogy n=k-ra is igaz.
Vegyünk egy olyan oszlopot, amelyben van legalább egy megjelölt mező. Ezt cseréljük ki a bal szélső oszloppal. Vegyünk egy olyan sort, amely üres (ilyen biztosan létezik, mert legfeljebb n-1 megjelölt mező van és ennél több, n sor), és cseréljük ki a legfelső sorral. Ezzel elérjük, hogy a legfelső sorban ne legyen megjelölt mező, a bal szélső oszlopban pedig legalább egy legyen.
Tekintsük most azt az (n-1)×(n-1)-es négyzetet, amelyet az első sor és az első oszlop elhagyásával kapunk. Ebben a négyzetben legfeljebb n-2 megjelölt mező van, ezért az indukciós feltevés szerint sor- és oszlopcserékkel a megjelölt elemeket a főátlója, egyben az eredeti főátló alá rendezhetjük. A cserék során az első oszlopot és sort már nem cseréljük fel más oszloppal, illetve sorral, ezért bár az első oszlopban levő megjelölt mező(k) helye megváltozhat az oszlopon belül, nem kerülhetnek a legfelső helyre, tehát ezek is a főátló alatt maradnak. A cserék során tehát minden megjelölt mező a főátló alá kerül.

 Pap Gyula (Debrecen, Fazekas M. Gimn., II. o.t.)