A B. 4432. feladat (2012. március)

B. 4432. A számítógép képernyőjén egy 98×98-as sakktábla látható, a szokásos módon színezve. Az egér segítségével kijelölhetünk tetszőleges olyan téglalapot, amelyet a sakktábla vonalai határolnak, majd rákattintva az ebben a téglalapban lévő mezők színe ellenkezőjére változik. Minimálisan hány kattintás szükséges ahhoz, hogy a sakktábla teljesen egyszínű legyen?

(5 pont)

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

Megoldás. Feltehetjük, hogy a bal felső sarokban fekete színű mező áll. Számozzuk meg a sorokat és az oszlopokat felülről lefelé, illetve balról jobbra haladva 1-től 98-ig. Minden sor megfelel egy \(\displaystyle 1\times 98\)-as, minden oszlop pedig egy \(\displaystyle 98\times 1\)-es téglalapnak, mely az egérrel kijelölhető. Így a páratlan sorszámú sorokat egymás után kijelölve, 49 kattintással elérhetjük, hogy minden páratlan sorszámú sorban a mezők színe ellenkezőjére változzon. Ekkor minden páratlan sorszámú oszlopban az összes mező színe fekete, míg a páros sorszámúakban minden mező színe fehér lesz. További 49 kattintással elérhetjük, hogy a páratlan sorszámú oszlopokban a mezők színe feketéről fehérre változzék. Ekkor már az összes mező fehér színű lesz, vagyis összesen 98 kattintás elegendő ahhoz, hogy a sakktábla teljesen egyszínű legyen.

Most megmutatjuk, hogy ennel kevesebb kattintás nem elegendő. Ehhez tekintsük a sakktábla szélén található \(\displaystyle 4\cdot 97\) mezőt, pontosabban közülük a szomszédosakat elválasztó \(\displaystyle 4\cdot 97\) darab egység hosszúságú szakaszt. Kezdetben minden egyes ilyen szakasz két ellenkező színű mezőt választ el. Amikor a sakktábla teljesen egyszínű, akkor viszont egyetlen ilyen elválasztás sincsen. A lehetséges esetek végiggondolásával könnyen látható, hogy minden egyes kattintással legfeljebb 4 elválasztás szüntethető meg. Ezért legalább 97 kattintás mindenképpen szükséges.

Tegyük fel most, hogy a feladat megoldható pontosan 97 kattintás elvégzésével. Ekkor minden egyes kattintással pontosan 4 elválasztást kell megszüntetnünk. Egy kattintás csak akkor szüntethet meg pontosan 4 elválasztást, ha a kijelölt téglalap vagy egy ``vízszintes'' \(\displaystyle k\times 98\)-as téglalap, melynek vízszintes szélei nem esnek egybe a sakktábla vízszintes széleivel, vagy pedig egy ``függőleges'' \(\displaystyle 98\times k\)-as téglalap, melynek függőleges szélei nem esnek egybe a sakktábla függőleges széleivel. Továbbá egy ilyen vízszintes téglalapra kattintva csak vízszintes szakaszok menti elválasztás szüntethető meg, függőleges téglalapra kattintva pedig csak függőleges szakaszok menti elválasztás szüntethető meg. A 97 kattintás közül vagy vízszintes, vagy függőleges kattintásból legfeljebb 48-at hajthatunk végre. Ha viszont legfeljebb 48 vízszintes (függőleges) kattintást végzünk, akkor a \(\displaystyle 2\cdot 97=194\) vízszintes (függőleges) elválasztás közül csak legfeljebb \(\displaystyle 4\cdot48=192\) szűnhet meg, ami nem elegendő.

Statisztika:

55 dolgozat érkezett.
5 pontot kapott:	Ágoston Péter, Ágoston Tamás, Árkos Gergely, Énekes Tamás, Géczi Péter Attila, Gyarmati Máté, Havasi 0 Márton, Herczeg József, Homonnay Bálint, Janzer Barnabás, Janzer Olivér, Maga Balázs, Mester Márton, Mihálykó András, Mócsy Miklós, Ódor Gergely, Schwarcz Tamás, Strenner Péter, Tardos Jakab, Viharos Andor, Zilahi Tamás.
2 pontot kapott:	2 versenyző.
1 pontot kapott:	27 versenyző.
0 pontot kapott:	5 versenyző.

A KöMaL 2012. márciusi matematika feladatai