Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem B. 4532. (April 2013)

B. 4532. In a given n×n table, n-1 fields are marked. A move consists in interchanging two rows or two columns. Is it always possible to carry out an appropriate sequence of such moves, so that all marked fields terminate under the main diagonal? (The main diagonal of a table connects the top left and bottom right corners.)

(Matlap, Kolozsvár)

(4 pont)

Deadline expired on May 10, 2013.


Sorry, the solution is available only in Hungarian. Google translation

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\ge1, é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.


Statistics:

66 students sent a solution.
4 points: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 points:Nagy Simon József, Németh Gergely, Simkó Irén.
2 points:4 students.
1 point:2 students.
0 point:29 students.

Problems in Mathematics of KöMaL, April 2013