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