Az A. 881. feladat (2024. május)

A. 881. Egy királlyal bejárjuk egy (a szokásos módon színezett) \(\displaystyle n \times n\)-es sakktábla minden mezőjét pontosan egyszer. Határozzuk meg, hogy legkevesebb hányszor kellett színt váltanunk a séta során.

Javasolta: Pálvölgyi Dömötör (Budapest)

(7 pont)

A beküldési határidő 2024. június 10-én LEJÁRT.

Megoldás. Azt állítjuk, hogy ha \(\displaystyle n\) páratlan, akkor a megoldás \(\displaystyle 2n-2\), míg ha \(\displaystyle n\) páros, akkor a megoldás \(\displaystyle n-1\). Ezekre példa konstrukció az alsó ábrákon zöld vonallal jelzett útvonal. Általánosan azt csináljuk, hogy végigmegyünk fentről lefelé párosával a sorokon, minden sorokból álló párt az ábra mintájára átlós lépésekkel bejárunk. Ekkor mindig csak a sorok végén kell színt váltanunk, illetve amikor átlépünk a következő párra. Így páros esetben végig is érünk, összesen \(\displaystyle n-1\) színváltással, páratlan esetben pedig az alsó sor kimarad, amin egyszerűen egyenesen végigmegyünk, ami további \(\displaystyle n-1\) színváltást eredményez.

Térjünk rá az alsó becslésre, hogy miért nem lehet ennél kevesebb. Legyen \(\displaystyle n\) rögzített, és színezzük úgy a táblázatot, hogy a bal felső sarka sötét. Osszuk a táblát régiókra, aszerint, hogy a király hány lépés alatt tud a pálya szélére jutni. Tehát a \(\displaystyle k\). régió éppen azokból a mezőkből áll, melyekre a király \(\displaystyle k\) lépéssel ki tud érni a pálya szélére, de kevesebbel nem (a pálya szélső mezői alkotják a 0. régiót). A fenti ábrák mutatják, hogyan néznek ki a régiók, a régiókat a piros vonalak határolják. Nevezzünk egy mezőt párosnak, ha páros indexű régióban van, különben páratlannak.

A megoldás fő gondolata a következő. Összesen sokkal több páros sötét mező van, mint páratlan, és általában a király egy páros fekete mezőről nem tud páros fekete mezőbe lépni. Számoljuk ezt ki precízen, és éppen azt a becslést fogjuk kapni, amire már mutattunk konstrukciót. Ahogy a konstrukciónál, itt is más lesz a számolás \(\displaystyle n\) paritásától függően.

1. eset: \(\displaystyle n\) páratlan.

Legyen \(\displaystyle n=2k+1\). Figyeljük meg, hogy ekkor \(\displaystyle k+1\) régió van, 0-tól \(\displaystyle k\)-ig számozva. Nyilván a \(\displaystyle k\). régióban 1, a \(\displaystyle (k-1)\)-ben 4 sötét mező van. Ezek után látható, hogy ahogy lépkedünk kifelé mindig 4-gyel több sötét mező van, mint az eggyel beljebbi szinten, azaz a \(\displaystyle (k-m)\). szinten éppen \(\displaystyle 4m\) minden \(\displaystyle 1 \leq m \leq k\) esetén. Indukcióval gondoljuk meg, hogy éppen \(\displaystyle (2k+1)\)-gyel van több páros sötét mező, mint a páratlan. Ez \(\displaystyle k=0\)-re világos, tegyük fel, hogy már \(\displaystyle (k-1)\)-re beláttuk. Ekkor egy \(\displaystyle (2k+1) \times (2k+1)\)-es táblázatban, ha a külső, 0. rétegtől eltekuntünk, akkor éppen visszakapunk egy eggyel kisebb esetet, egy \(\displaystyle (2k-1) \times (2k-1)\)-es táblázatot, amiben már tudjuk, hogy \(\displaystyle (2k-1)\)-gyel van több páros sötét mező, mint páratlan sötét mező. Ám ha visszarakjuk a külső régiót, akkor ami eddig párosadik régió volt, az páratlan lesz, és fordítva, így a 0. régió sötét mezőin kívül \(\displaystyle (2k-1)\)-gyel több a páratlan sötét mező, és ehhez még hozzáadva a 0. régió \(\displaystyle 4k\) darab sötét mezőjét, éppen megkapjuk, hogy összesen \(\displaystyle (2k+1)\)-gyel van több páros sötét mező, ahogy akartuk.

Tegyük fel, hogy adott egy bejárása a királynak, melyben minden mezőn pontosan egyszer járt. Mondjuk azt, hogy két szomszédos mező barátságban van egymással, ha a király az útja során az egyik mezőről rálépett a másikra, és egy mező barátai azok a mezők, akivel ő barátságban van. Ekkor a király útján a kezdő és a végpont kivételével (akiknek egy barátja van) minden mezőnek pontosan két barátja van, egy ahonnan érkezett, és egy ahova lépett a király. Vizsgáljuk meg a páros sötét mezők barátait. Legyen \(\displaystyle a\) a páros sötét mezők száma (ezt könnyedén ki is tudnánk pontosan számolni, de nem lesz rá szükség), ekkor \(\displaystyle a-2k-1\) páratlan sötét mező van. Figyeljük meg, hogy páros sötét mezőből nem lehet páros sötét mezőbe lépni. Az \(\displaystyle a\) darab sötét mezőnek legalább \(\displaystyle 2a-2\) barátja van összesen, multiplicitással, míg a páratlan sötét mezőknek legfeljebb \(\displaystyle 2(a-2k-1)\), így van legalább

\(\displaystyle 2a-2-2(a-2k-1)=4k=2n-2\)

olyan barátságban álló pár, akiknek az egyik tagja páros sötét, és a másik nem páratlan sötét. Ám ekkor a másik pár csak világos mező lehet, és ez éppen azt jelenti, hogy a király útja során történt \(\displaystyle 2n-2\) színváltás.

2. eset: \(\displaystyle n\) páros

Legyen \(\displaystyle n=2k\). Ez az eset nagyon hasonlóan működik, két apró különbség van: vannak szomszédos páros sötét mezők, illetve a király sétája garantáltan különböző színű mezőn végződik, mint ahol indul. De ezek nem nehezítnek a számolásban, így itt már kevésbé megyünk bele a részletekbe.

Ebben az esetben is bentről kifelé négyesével nő a régiókban lévő sötét mezők száma, így ekkor is egyszerű indukció mutatja, hogy \(\displaystyle 2k\)-val van több páros sötét mező, mint páratlan. Itt is \(\displaystyle k\) darab régió van, minden régióban van pontosan két pár sötét mező, akik szomszédosak egymással, kivéve a középső, \(\displaystyle (k-1)\). régióban, mert ott csak egy ilyen pár van. Megint vegyünk egy tetszőleges sétát, használjuk az előző esetben bevezetett elnevezéseket, és legyen \(\displaystyle a\) a páros sötét mezők száma, ekkor \(\displaystyle a-2k\) páratlan sötét mező van. Mivel nem kezdődhet és végződhet egyszerre sötét mezőn a király sétája, így az \(\displaystyle a\) páros sötét mezőnek összesen van legalább \(\displaystyle 2a-1\) barátja multiplicitással.

Ha \(\displaystyle k\) páros, akkor \(\displaystyle \frac{k}{2}\) páros indexű régió van, és a középső \(\displaystyle (k-1)\). nem ilyen, így \(\displaystyle k\) olyan páros sötét mezőkből álló pár van, akik szomszédosak. Ha \(\displaystyle k\) páratlan, akkor \(\displaystyle \frac{k+1}{2}\) páros indexű régió van, köztük a középső, \(\displaystyle (k-1)\). is, így ebben az esetben is \(\displaystyle k\) olyan páros sötét mezőkből álló pár van, akik szomszédosak. Tehát páros sötét mezőknek összesen legfeljebb \(\displaystyle 2k\) páros sötét barátja lehet multiplicitással.

A páratlan sötét mezőknek legfeljebb \(\displaystyle 2(a-2k)\) barátja van multiplicitással, így van legalább

\(\displaystyle (2a-1)-(2k)-2(a-2k)=2k-1=n-1\)

olyan barátja páros sötét mezőknek (multiplicitással), ami se nem páros, se nem páratlan sötét mező, azaz világos. Éppen ezt akartuk megmutatni.

Statisztika:

14 dolgozat érkezett.
7 pontot kapott:	Bodor Mátyás, Czanik Pál, Holló Martin, Kocsis 827 Péter, Varga Boldizsár.
6 pontot kapott:	Szakács Ábel, Wiener Anna.
5 pontot kapott:	1 versenyző.
3 pontot kapott:	1 versenyző.
2 pontot kapott:	2 versenyző.
0 pontot kapott:	1 versenyző.
Nem számítjuk a versenybe a születési dátum vagy a szülői nyilatkozat hiánya miatt:	2 dolgozat.

A KöMaL 2024. májusi matematika feladatai