KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

MBUTTONS

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

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 points)

Deadline expired on 10 May 2013.


Google Translation (Sorry, the solution is published in Hungarian only.)

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 on problem B. 4532.
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

  • Támogatóink:   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