Problem B. 4132. (December 2008)

B. 4132. Annie and Bonnie are playing the following game on a 2008×2008 chessboard: Annie selects a few fields of the board but does not tell Bonnie which. Then she writes in each field the number of selected fields that it is connected to by an edge or vertex. Is that enough information for Bonnie to tell which fields were selected? What is the answer if they play on a 2009×2009 board?

Suggested by D. Nagy

(5 pont)

Deadline expired on January 15, 2009.

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

Megoldás: Egy pozitív egész számot nevezzünk szépnek, ha 3-mal osztva 1 maradékot ad. Az n×n-es sakktábla sorait és oszlopait is számozzuk meg sorban 1-től n-ig, és egy sort vagy oszlopot nevezzünk szépnek akkor, ha sorszáma szép. Egy mező szép, ha sor- és oszlopindexe is szép, átlagos, ha ha sor- és oszlopindexe közül pontosan az egyik szép, egyébként pedig csúnya. Tegyük fel, hogy az n szám 3-mal osztva 2 maradékot ad, és Aranka éppen a szép mezőket választotta ki. Ekkor minden mezőre 1-et fog írni, akárcsak abban az esetben, ha azokat a mezőket választja ki, amelyeknek sor- és oszlopindexe is 2 maradékot ad 3-mal osztva. Ezért ha 2009×2009-es táblán játszanak, akkor nem biztos, hogy Bianka ki tudja találni, hogy mely mezőket választotta ki Aranka.

2008×2008-as táblán viszont, és általában egy n×n-es táblán is, ahol n szép, Bianka egyértelműen meg tudja mondani, hogy mely mezőket választotta ki Aranka. A sakktábla egy részét nevezzük kiszámolhatónak, ha Bianka meg tudja mondani, hogy az adott rész összesen hány kiválasztott mezőt tartalmaz. Elég azt megmutatni, hogy a sakktábla minden olyan része, amely egyetlen mezőből áll, kiszámolható. Nevezzük elemi téglalapnak a sakktábla 3×3-as résztábláit, a vízszintes szélek mentén található 2×3-as, illetve a függőleges szélek mentén található 3×2-es résztáblákat, valamint a sarkokban elhelyezkedő 2×2-es résztáblákat. Az ábra szerint minden elemi téglalapnak van egy `közepe', amelyre írt szám megegyezik azoknak a mezőknek a számával, amelyeket Aranka a szóban forgó elemi téglalapból kiválasztott. Más szóval, minden elemi téglalap kiszámolható.

Mivel a teljes sakktábla felbontható elemi téglalapokra, a sakktábla kiszámolható, továbbá a sakktábla egy része pontosan akkor kiszámolható, ha a komplementere kiszámolható. Könnyen látható, hogy tetszőleges szép sor komplementere felbontható elemi téglalapokra, vagyis tetszőleges szép sor kiszámolható. Nyilván ugyanez igaz a szép oszlopokra is. Tekintsünk egy szép mezőt. Ha az ezt tartalmazó sort és oszlopot is elhagyjuk, a megmaradt rész felbontható elemi téglalapokra. Ezért az adott mezőt tartalmazó sor és oszlop egyesítéséből álló `kereszt' kiszámolható. Ha a sorban lévő kiválasztott mezők számához hozzáadjuk az oszlopban lévő kiválasztott mezők számát, majd kivonjuk a keresztben lévő kiválasztott mezők számát, az eredmény pontosan akkor lesz 1, ha az adott mező szerepel a kiválasztottak között. Ez azt jelenti, hogy minden egyes szép mező kiszámolható.

Most megmutatjuk, hogy minden átlagos mező is kiszámolható. Szimmetria okok miatt feltehetjük, hogy a mezőnek a sorindexe szép, vagyis a mező sora kiszámolható. A mező oszlopindexe 3-mal osztva 0 vagy 2 maradékot ad, ennek megfelelően vagy a tőle közvetlenül jobbra, vagy a tőle közvetlenül balra lévő oszlop szép. Tekintsük azt a dupla oszlopot, amely ebből a szép oszlopból és a mezőt tartalmazó oszlopból áll. Ennek a dupla oszlopnak a komplementere is felbontható elemi téglalapokra, vagyis a dupla oszlop kiszámolható. Hasonlóképpen, a dupla oszlop és a mezőt tartalmazó sor egyesítésével kapott kereszt is kiszámolható, ezek alapján pedig kiszámolható az az 1×2-es téglalap is, amely a sor és a dupla oszlop metszeteként áll elő. Ez a téglalap a szóban forgó átlagos mező mellett még egy szép mezőt tartalmaz, ami kiszámolható, és ezért a szóban forgó átlagos mező is kiszámolható.

Már csak azt kell igazolni, hogy a csúnya mezők is kiszámolhatók. Egy ilyen mező sarkosan érintkezik egy szép mezővel, és ezek együtt egy olyan 2×2-es négyzet két átellenes sarokmezőjét alkotják, melyben a másik két mező átlagos. Elég tehát annyit megmutatni, hogy ez a 2×2-es négyzet kiszámolható. Ez azonban rögtön következik abból, hogy mind az őt tartalmazó dupla sor, az őt tartalmazó dupla oszlop, és az e kettő egyesítéseként kapott kereszt kiszámolható.

Statistics:

32 students sent a solution.
5 points:	Ágoston Tamás, Blázsik Zoltán, Bodor Bertalan, Éles András, Énekes Péter, Fonyó Dávid, Kalina Kende, Kiss 902 Melinda Flóra, Lovas Lia Izabella, Márkus Bence, Mester Márton, Nagy 648 Donát, Nagy Róbert, Perjési Gábor, Strenner Péter, Szenczi Zoltán, Varga 171 László, Viharos Andor, Weisz Ágoston.
3 points:	4 students.
2 points:	6 students.
0 point:	2 students.
Unfair, not evaluated:	1 solutions.

Problems in Mathematics of KöMaL, December 2008