Problem B. 5190. (October 2021)

B. 5190. In a table of \(\displaystyle n\) rows and \(\displaystyle k\) columns, there is \(\displaystyle -1\) written in each field. In each move, one row and one column is selected. Each number in the row is changed to the opposite, and then each number in the column is changed to the opposite.

For what values of \(\displaystyle n\) and \(\displaystyle k\) is it possible to achieve a value of \(\displaystyle +1\) in every field of the whole table?

Proposed by J. Szoldatics, Budapest

(3 pont)

Deadline expired on November 10, 2021.

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

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.

Statistics:

151 students sent a solution.
3 points:	100 students.
2 points:	22 students.
1 point:	12 students.
0 point:	8 students.
Unfair, not evaluated:	2 solutionss.
Not shown because of missing birth date or parental permission:	1 solutions.

Problems in Mathematics of KöMaL, October 2021