KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

Kifordítható

tetraéder

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

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 points)

Deadline expired on 10 April 2012.


Google Translation (Sorry, the solution is published in Hungarian only.)

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 on problem B. 4432.
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

  • Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley