A B. 5190. feladat (2021. október)

B. 5190. Egy \(\displaystyle n\) sorból és \(\displaystyle k\) oszlopból álló táblázat mindegyik mezőjébe \(\displaystyle -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 \(\displaystyle n\) és \(\displaystyle k\) esetén érhető el, hogy mindegyik mezőben \(\displaystyle 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 \(\displaystyle nk\) páros (azaz, ha \(\displaystyle n\) és \(\displaystyle k\) közül legalább az egyik páros).

Először tegyük fel, hogy \(\displaystyle n\) páros. Hajtsuk végre azt az \(\displaystyle 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 \(\displaystyle (n+1)\)-szer változtatjuk, ami \(\displaystyle 2\mid n\) alapján páratlan sok változtatást jelent, így végül szintén 1-esek lesznek. Vagyis, ha \(\displaystyle n\) páros, akkor elérhető a csupa-1 állapot.

Ha \(\displaystyle 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 \(\displaystyle n\) és \(\displaystyle k\) is páratlan. Egy lépésben mindig \(\displaystyle 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 \(\displaystyle (-1)^{nk}=-1\), így a csupa-1 állapot nem érhető el.

Ezzel beláttuk, hogy a csupa-1 állapot pontosan akkor érhető el, ha \(\displaystyle 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