KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

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.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley