 |
A B. 4532. feladat (2013. április) |
B. 4532. Adott egy n×n-es táblázat, amelyben megjelöltünk n-1 mezőt. Egy lépés során felcserélhetünk két sort vagy két oszlopot. El lehet-e mindig érni ilyen lépésekkel, hogy az összes megjelölt mező a főátló alatt legyen? (A főátló a táblázat bal felső és jobb alsó sarkát köti össze.)
Matlap, Kolozsvár)
(4 pont)
A beküldési határidő 2013. május 10-én LEJÁRT.
Megoldási ötlet: Teljes indukció.
Megoldás. Az állítást pontosan n-1 helyett legfeljebb n-1 megjelölt mezőre bizonyítjuk, a megjelölt mezők száma szerinti indukcióval.
Legyen a megjelölt mezők száma k. Ekkor tehát n>k. Ha k=0, akkor nincs egy megjelölt mező sem, és az állítás triviális. Tegyük tehát fel, hogy k
1, és az állítás igaz kisebb értékekre.
Mivel több oszlop van, mint megjelölt mező, van olyan oszlop, amiben egy megjelölt mező sincs. Cseréljük ki az utolsó oszlopot egy ilyennel. Ezután pedig az utolsó sort cseréljük fel egy olyan sorral, amelyben van legalább egy megjelölt mező.
A táblázat bal felső, (n-1)×(n-1) méretű részében legfeljebb k-1<n-1 megjelölt mező lehet. Az indukciós feltevés szerint ezeket a főátló alá rendezhetjük úgy, hogy csak az első n-1 sort és oszlopot rendezzük át. A végső állapotban ezért az utolsó oszlop üres marad, és az első n-1 oszlopban sincsenek megjelölt mezők a főátlón vagy afölött.
Statisztika:
66 dolgozat érkezett. 4 pontot kapott: Badacsonyi István András, Baran Zsuzsanna, Bereczki Zoltán, Bingler Arnold, Csépai András, Fehér Zsombor, Fekete Panna, Fonyó Viktória, Forrás Bence, Gyulai-Nagy Szuzina, Hansel Soma, Janzer Barnabás, Janzer Olivér, Kabos Eszter, Katona Dániel, Kovács 972 Márton, Kovács Balázs Marcell, Lőrinczy Zsófia Noémi, Makk László, Nagy Róbert, Petrényi Márk, Porupsánszki István, Somogyvári Kristóf, Szabó 157 Dániel, Szabó 789 Barnabás, Tóth László Gábor, Vető Bálint, Zilahi Tamás. 3 pontot kapott: Nagy Simon József, Németh Gergely, Simkó Irén. 2 pontot kapott: 4 versenyző. 1 pontot kapott: 2 versenyző. 0 pontot kapott: 29 versenyző.
A KöMaL 2013. áprilisi matematika feladatai