Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem B. 4432. (March 2012)

B. 4432. There is a 98×98 chessboard on the monitor of a computer. With the mouse, you can select a rectangle bounded by lattice lines of the chessboard. If you click on the rectangle, each chessboard field inside it will change to the opposite colour. What is the minimum number of clicks needed to make the whole chessboard have the same colour.

(5 pont)

Deadline expired on April 10, 2012.


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

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ő.


Statistics:

55 students sent a solution.
5 points:Á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 points:2 students.
1 point:27 students.
0 point:5 students.

Problems in Mathematics of KöMaL, March 2012