A B. 4781. feladat (2016. március)

B. 4781. Egy \(\displaystyle n \times n\)-es sakktábla sorait is és oszlopait is sorban megszámoztuk az 1-től \(\displaystyle n\)-ig terjedő számokkal, majd minden mezőjére egy-egy pénzérmét helyeztünk el. A következő játékot játsszuk: kiválasztunk a táblán egy írással felfelé elhelyezett érmét. Amennyiben sorának és oszlopának sorszámai \(\displaystyle k\), illetve \(\displaystyle m\), akkor az összes olyan érmét átfordítjuk, amelynek sora legalább \(\displaystyle k\), oszlopa pedig legalább \(\displaystyle m\) indexű. Ezt a lépést ismételgetjük.

Mi az a legkisebb \(\displaystyle L(n)\) szám, amire igaz, hogy tetszőleges kezdő állásból kiindulva legfeljebb \(\displaystyle L(n)\) lépésben elérhetjük, hogy minden érmén a fej legyen felül?

Javasolta: Lenger Dániel és Szoldatics József (Budapest)

(6 pont)

A beküldési határidő 2016. április 11-én LEJÁRT.

Megoldás. Először belátjuk, hogy a feladat feltételeit kielégítő \(\displaystyle L(n)\) szám létezik, és megmutatjuk, hogy \(\displaystyle L(n)\leq n^2\). Ehhez azt kell igazolnunk, hogy bármilyen kezdőállapotból legfeljebb \(\displaystyle n^2\) lépésben elérhető, hogy minden érmén a fej legyen felül. Számozzuk meg a mezőket 1-től \(\displaystyle n^2\)-ig a következő módon: az \(\displaystyle i\)-edik sor \(\displaystyle j\)-edik mezőjének sorszáma legyen \(\displaystyle n(i-1)+j\). Amikor egy forgatásos lépést végrehajtunk egy mező szerint, akkor a nála kisebb sorszámú mezők egyikén sem fordítunk át érmét. Kövessük a következő stratégiát: minden lépésben válasszuk ki a legkisebb sorszámú mezőt, amelyen írás van, és forgassuk át a megfelelő érméket. Ha ezt a stratégiát követjük, akkor a legkisebb sorszámú írást tartalmazó mező sorszáma minden lépésben legalább 1-gyel nő. Ugyanis csökkenni nem tud, mert mindig csak írást tartalmazó mező szerint forgatunk, egy ilyen forgatás viszont a kisebb sorszámú (már fejet tartalmazó) mezőket nem érinti. Továbbá az éppen kiválasztott mezőn írásból fej lesz, ezért a kérdéses sorszám változatlan sem maradhat, így valóban legalább 1-gyel nő. A sorszám értéke 1 és \(\displaystyle n^2\) közötti, így legfeljebb \(\displaystyle n^2\) lépés után további már nem hajtható végre, ami azt jelenti, hogy minden mezőn fej van. Ezzel megmutattuk, hogy legfeljebb \(\displaystyle n^2\) lépésben mindig elérhető, hogy minden mezőn fej legyen, vagyis \(\displaystyle L(n)\leq n^2\).

Most mutatunk egy olyan esetet, amikor szükség van \(\displaystyle n^2\) lépésre. Legyen kezdetben az \(\displaystyle i\)-edik sor \(\displaystyle j\)-edik mezőjén írás, ha \(\displaystyle ij\) páratlan és fej, ha \(\displaystyle ij\) páros. Azt állítjuk, hogy minden mező szerint páratlan sokszor kell forgatnunk, ha el akarjuk érni a csupa-fej állapotot. Az 1-es sorszámú mező kezdetben írás, hiszen \(\displaystyle 1\cdot 1\) páratlan, a végén fejnek kell lennie, így az első mező szerint valóban páratlan sokszor kell forgatnunk. (Valójában az is könnyen megmutatható, hogy pontosan egyszer.) Tegyük fel, hogy már beláttuk, hogy a csupa-fej állapot eléréséig a \(\displaystyle k\)-nál kisebb sorszámú mezők mindegyike szerint páratlan sokszor forgattunk. Legyen a \(\displaystyle k\)-adik mező az \(\displaystyle i\)-edik sor \(\displaystyle j\)-edik mezője. Ezen a mezőn kezdetben pontosan akkor volt írás, ha \(\displaystyle ij\) páratlan. A \(\displaystyle k\)-adik mezőn lévő érmét akkor fordítjuk át, ha egy olyan mező szerint forgatunk, amely az első \(\displaystyle i\) sor valamelyikében és az első \(\displaystyle j\) oszlop valamelyikében van. Ezen \(\displaystyle ij\) mező egyike éppen a \(\displaystyle k\)-adik mező, a többi mező pedig \(\displaystyle k\)-nál kisebb sorszámú. Az indukciós feltevés szerint ezek mindegyike szerint páratlan sok forgatás történik. Ha \(\displaystyle ij\) páros, akkor kezdetben a \(\displaystyle k\)-adik mezőn fej volt, a kisebb sorszámú mezők szerint páratlan sok olyan forgatás történik, aminél a \(\displaystyle k\)-adik mezőn lévő érmét is átfordítjuk, ezért a \(\displaystyle k\)-adik mező szerint is páratlan sokszor kell forgatnunk, hogy végül fejre változzon. Ha \(\displaystyle ij\) páratlan, akkor a \(\displaystyle k\)-adik mezőn kezdetben írás volt, a kisebb sorszámú mezők szerint páros sok olyan forgatás történik, melynél a \(\displaystyle k\)-adik mezőn lévő érme is fordul, így ahhoz, hogy az végül fejre változzon, a \(\displaystyle k\)-adik mező szerint páratlan sokszor kell forgatnunk. Ezzel beláttuk, hogy mind az \(\displaystyle n^2\) mező szerint páratlan sokszor kell, így a lépések száma legalább \(\displaystyle n^2\). Tehát \(\displaystyle L(n)=n^2\).

Statisztika:

68 dolgozat érkezett.
6 pontot kapott:	Alexy Milán, Andó Angelika, Baran Zsuzsanna, Bindics Boldizsár, Bodolai Előd, Bukva Balázs, Busa 423 Máté, Csorba Benjámin, Döbröntei Dávid Bence, Fuisz Gábor, Gáspár Attila, Győrffy Ágoston, Hansel Soma, Hraboczki Attila Márton, Imolay András, Kerekes Anna, Keresztfalvi Bálint, Klász Viktória, Kovács 162 Viktória, Kovács 246 Benedek, Kőrösi Ákos, Kuchár Zsolt, Lajkó Kálmán, Lajos Hanka, Lakatos Ádám, Márton Dénes, Matolcsi Dávid, Molnár Bálint, Molnár-Sáska Zoltán, Nagy Dávid Paszkál, Nagy Kartal, Németh 123 Balázs, Nguyen Viet Hung, Polgár Márton, Saár Patrik, Schrettner Jakab, Somogyi Pál, Souly Alexandra, Sudár Ákos, Szabó 417 Dávid, Szabó Kristóf, Szakály Marcell, Tiszay Ádám, Tóth Viktor, Tran 444 Ádám, Vágó Ákos, Váli Benedek, Vári-Kakas Andor, Weisz Máté, Zólomy Kristóf.
5 pontot kapott:	10 versenyző.
4 pontot kapott:	1 versenyző.
3 pontot kapott:	5 versenyző.
0 pontot kapott:	2 versenyző.

A KöMaL 2016. márciusi matematika feladatai