 |
A B. 5190. feladat (2021. október) |
B. 5190. Egy n sorból és k oszlopból álló táblázat mindegyik mezőjébe −1 van írva. Egy lépésben egy sort és egy oszlopot kijelölünk és előbb a kijelölt sor, majd a kijelölt oszlop mindegyik számát az ellentettjére változtatjuk.
Mely n és k esetén érhető el, hogy mindegyik mezőben 1-esek legyenek?
Javasolta: Szoldatics József (Budapest)
(3 pont)
A beküldési határidő 2021. november 10-én LEJÁRT.
Megoldás. Azt fogjuk megmutatni, hogy ez pontosan akkor érhető el, ha nk páros (azaz, ha n és k közül legalább az egyik páros).
Először tegyük fel, hogy n páros. Hajtsuk végre azt az n lépést, amikor a kiválaszott oszlop mindig az első, a kiválasztott sor pedig mindig különböző. Ekkor az első oszlopon kívüli elemeket 1-szer változtatjuk, így 1-esek lesznek. Az első oszlopon belüli elemeket pedig (n+1)-szer változtatjuk, ami 2∣n alapján páratlan sok változtatást jelent, így végül szintén 1-esek lesznek. Vagyis, ha n páros, akkor elérhető a csupa-1 állapot.
Ha k páros, akkor ugyanez a módszer működik, a sorok és oszlopok szerepét megcserélve.
Végül tegyük fel, hogy n és k is páratlan. Egy lépésben mindig n+k változtatás történik, ami egy páros szám. Így a táblázatban lévő elemek szorzata végig változatlan marad. A csupa-1 táblázat esetében a szorzat 1 lenne, azonban a kiindulási állapotban a szorzat (−1)nk=−1, így a csupa-1 állapot nem érhető el.
Ezzel beláttuk, hogy a csupa-1 állapot pontosan akkor érhető el, ha nk páros.
Statisztika:
151 dolgozat érkezett. 3 pontot kapott: 100 versenyző. 2 pontot kapott: 22 versenyző. 1 pontot kapott: 12 versenyző. 0 pontot kapott: 8 versenyző. Nem versenyszerű: 2 dolgozat. Nem számítjuk a versenybe a születési dátum vagy a szülői nyilatkozat hiánya miatt: 1 dolgozat.
A KöMaL 2021. októberi matematika feladatai
|
|