Kezdőlap


Feladat:	Gy.2497	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Kiss Gyula , Limbek Réka
Füzet:	1989/február, 68 - 69. oldal		PDF \| MathML
Témakör(ök):	Egyenlőtlenségek, Algoritmikus eljárások, Sakk, Gyakorlat
Hivatkozás(ok):	Feladatok: 1988/szeptember: Gy.2497

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

I. megoldás. A feladat kérdésére igen a válasz; megmutatjuk, hogy a sakktábla soronként kiüríthető. Tekintsük ehhez a következő műveleteket:
(1) Ha egy sor minden mezőjén egy búzaszem van, akkor vegyük el minden mezőről ezt az egy szemet.
(2) Ha egy sor minden mezőjén egynél több búzaszem van, akkor vegyünk el minden mezőről egy szemet.
(3) Ha egy sorban van olyan $M$ -mező, amelyen egy búzaszem van, de a sorban nem mindegyik mező ilyen, akkor az összes ilyen $M$ mező oszlopában kétszerezzük meg a búzaszemek számát.
Tetszőleges, üres mezőt nem tartalmazó sort kiválasztva látható, hogy amíg ez a sor teljesen ki nem ürül, az (1), (2), ill. (3) műveletek közül mindig pontosan egy hajtható végre. A sorban levő búzaszemek száma az (1)-es vagy a (2)-es művelet során 8-cal, a (3)-as művelet alkalmazásakor pedig legalább 1-gyel (és legfeljebb 7-tel) csökken. Minden egyes művelet végrehajtásával tehát csökken a búzaszemek száma a kiszemelt sorban, így ott előbb-utóbb 8-nál kevesebb búzaszem marad. Mivel sem a (2)-es, sem a (3)-as művelet nem hoz létre üres mezőt, ezért ez csak úgy lehetséges, ha éppen 8 szem maradt a sorban, minden mezőn 1-1. A sor tehát a következő (1)-es lépésben kiürül.
Ha egy sor már üres, akkor a további sorok kiürítésekor ide már nem kerülhet búzaszem, így az eljárás sorról sorra haladva valóban véget ér.

Kiss Gyula (Zalaegerszeg, Zrínyi M. Gimn., II. o. t.)
dolgozata alapján

II. megoldás. Ismét soronként ürítjük ki a sakktáblát. Azt mutatjuk meg, hogy a megengedett lépések alkalmas sorozatával elérhető, hogy egy tetszőlegesen kiválasztott sor minden mezőjén ugyanannyi búzaszem maradjon, és eközben a további sorok üres mezői üresek maradnak, a nem üres mezők tartalma pedig nem csökken. A mezőnként azonos számú búzaszemek ilyenkor egyesével levehetők a tábláról, és az eljárás bármelyik (nem üres) soron folytatható.
Olyan módszert mutatunk be, amellyel egy adott nemüres sor két kijelölt mezőjén egyenlővé tehető a búzaszemek száma. A sor további mezőire ekkor csak annyiban leszünk tekintettel, hogy kiürülésüket megakadályozzuk, azaz, ha valamelyikükről az utolsó szemet kellene levenni, akkor a lépés előtt megduplázzuk az ott lévő búzaszemek számát.
Legyen a két mezőn

m_{1}

és

m_{2}

szem búza,

0 < m_{1} < m_{2}

. Nyilván létezik olyan

k

nemnegatív egész kitevő, amelyre

\begin{matrix} M_{1} = 2^{k} m_{1} < m_{2} < 2 M_{1}; \end{matrix}

a megfelelő mező oszlopában

k

-szor duplázzuk meg a búzaszemek számát, így ott éppen

M_{1}

darab szem lesz. Vegyünk el ezután ennek a sornak minden mezőjéről egyesével

2 M_{1} - m_{2}

szem búzát. Mivel

\begin{matrix} 0 ≦ 2 M_{1} - m_{2} < M_{1} < m_{2}, \end{matrix}

ezért ez megtehető anélkül, hogy a két mező bármelyike kiürülne. Így az egyik mezőn

\begin{matrix} m'_{1} = M_{1} - (2 M_{1} - m_{2}) = m_{2} - M_{1}, \end{matrix}

a másikon

\begin{matrix} m_{2}' = m_{2} - (2 M_{1} - m_{2}) = 2 (m_{2} - M_{1}) = 2 m'_{1} \end{matrix}

szem búza marad. Az előbbi mező tartalmát megduplázva mindkét mezőn egyaránt

m_{2}'

búzaszem lesz, és a sor további mezői közül egy sem válik üressé. Közülük egy újabbat választva, ennek a tartalma ugyanígy egyenlővé tehető az előbbi mezőkével, ha a fenti lépéseket az egyenlő tartalmú mezőkre egyformán hajtjuk végre. Az eljárást legfeljebb 7-szer ismételve végül elérhető, hogy a kiszemelt sor minden mezőjén ugyanannyi búzaszem legyen, és éppen ezt kívántuk bizonyítani.

Limbek Réka (Budapest, Fazekas M. Gyak. Gimn., II. o. t.)
dolgozata alapján