Az A. 865. feladat (2023. november)

A. 865. Keresztrejtvénynek nevezünk egy fekete és fehér négyzetekből álló négyzetrácsot, melyben minden fehér mezőhöz található egy őt tartalmazó \(\displaystyle {2\times 2}\)-es része a táblázatnak, amely csak fehér mezőkből áll. Szónak nevezzük a táblázat egy sorában vagy oszlopában található, csak fehér mezőkből (legalább kettőből) álló részét a táblázatnak, melyet mindkét végén fekete mező vagy a tábla széle határol.

Bizonyítsuk be, hogy egy \(\displaystyle n\times n\)-es keresztrejtvényben nem lehet több szó, mint \(\displaystyle \frac{{(n+1)}^2}{2}\).

Javasolta: Nikolai Beluhov (Bulgária)

(7 pont)

A beküldési határidő 2023. december 11-én LEJÁRT.

Csatoljunk a táblázathoz egy csak fekete mezőkből álló sort, illetve oszlopot jobbról és alulról. Innentől kezdve az így kapott \(\displaystyle (n+1)\times (n+1)\)-es táblázatban dolgozunk.

Stratégiánk lényege az, hogy a keresztrejtvényben szereplő minden szóhoz hozzárendelünk két mezőt. Azonban ez nem fog ilyen egyszerű formában működni, és a megoldás során felmerülő problémákat is orvosolni kell majd.

Vezessünk be egy koordinátarendszert olyan módon, hogy a bal alsó mező legyen a \(\displaystyle (0,0)\) pont, a jobb felső pedig \(\displaystyle (n,n)\). Ha a \(\displaystyle c\) mező koordinátái \(\displaystyle (x,y)\), akkor \(\displaystyle c+(u,v)\) az \(\displaystyle (x+u,y+v)\) mezőt jelöli.

A keresztrejtvényben szereplő minden egyes vízszintes szóhoz rajzoljunk egy nyilat, amely a legjobboldalibb mezőjéről mutat az őt jobbról lezáró fekete mezőre. Hasonlóan járjunk el a függőleges szavak esetén: razjoljunk egy nyilat, amely a szót alulról lezáró fekete mezőről mutat a közvetlenül felette lévő fehér mezőre (azért kellett a megoldás elején hozzáadni az extra sor és oszlop fekete mezőket, hogy a szavakat lezáró fekete mezők mindig létezzenek).

A nyilakból irányított utakat lehet alkotni, amelyek felfele és jobbra haladnak.

Egy \(\displaystyle c_1c_2c_3\) utat speciálisan nevezünk, ha \(\displaystyle c_1\) fehér, \(\displaystyle c_2\) fekete, \(\displaystyle c_3\) fehér, és \(\displaystyle c_2+(-1,1)\) fekete. Először a nem speciális utakkal foglalkozunk, és utána térünk rá a speciális utakra.

Legyen \(\displaystyle P=c_1c_2...c_{k+1}\) egy \(\displaystyle k\) darab nyílból álló nem speciális út. \(\displaystyle P\)-hez hozzá fogunk rendelni \(\displaystyle 2k\) darab mezőt olyan módon, hogy az útban szereplő \(\displaystyle k\) darab nyílhoz tartozó \(\displaystyle k\) szó közül minden egyeshez kettőt rendelünk hozzá: a \(\displaystyle P\) által érintett mezőket hozzárendeljük \(\displaystyle P\)-hez, továbbá \(\displaystyle 2\le i\le k\) esetén az \(\displaystyle a_i+(-1,1)\) mezőt is hozzárendeljük \(\displaystyle P\)-hez. Mivel minden egyes fehér mezőhöz lehet találni egy őt tartalmazó \(\displaystyle 2\times 2\)-es, csak fehér mezőkből álló részt, és mivel \(\displaystyle P\) nem speciális, az így definiált \(\displaystyle k-1\) darab mező mind fehér, és nem megy át rajtuk másik út. Így a \(\displaystyle P\)-hez rendelt mezőket tartalmazza \(\displaystyle P\) vagy fehér színűek.

Most foglalkozzunk a speciális utakkal.

Először minden egyes speciális úthoz rendeljük hozzá az általa érintett három mezőt.

Ezen a ponton egy fekete színű \(\displaystyle c\) mező pontosan akkor van hozzárendelve egy \(\displaystyle P\) úthoz, ha \(\displaystyle c+(0,1)\) és \(\displaystyle c+(-1,0)\) közül legalább az egyik fekete. Továbbá, egy fehér \(\displaystyle c\) mező pontosan akkor van hozzárendelve egy úthoz, ha a következők közül teljesül az egyik: (i) \(\displaystyle c+(1,0)\) és \(\displaystyle c+(0,-1)\) közül legalább az egyik fekete; (ii) mindkét mező fehér és \(\displaystyle c+(1,-1)\) fekete; (iii) az előző két esetben említett mindhárom mező fehér, továbbá \(\displaystyle c+(2,-1)\) és \(\displaystyle c+(1,-2)\) fekete.

Ezután a következő módon definiáljuk a extra átlót: az ábrán W jelöli a fehér mezőket, B a fekete mezőket és ? azokat a mezőket, melyeknem nem ismert a színe, de fontos a definícióhoz:

\(\displaystyle \begin{matrix} - & ? & - & - & - & - & - & -\\ ? & W & W & - & - & - & - & -\\ - & W & W & B & - &- &- &-\\ -& -& B& W& W& -& -& -\\ -& -& -& W& W& B& -& -\\ -& -& -& -& B& W& W& -\\ -& -& -& -& -& W& W& B\\ -& -& -& -& -& -& B& B\\ \end{matrix}\)

Minden egyes extra átló fehér kezdetű vagy fekete kezdetű. Ha a \(\displaystyle d\), \(\displaystyle d+(0,-1)\), \(\displaystyle d+(1,0)\) és \(\displaystyle d+(-1,1)\) mezők egy fehér mezőkből álló \(\displaystyle 2\times 2\)-es részt alkotnak, továbbá a \(\displaystyle d+(0,1)\) és \(\displaystyle d+(-1,0)\) mezők közül legalább az egyik fehér vagy a táblázaton kívülre esik, akkor ez az első fehér \(\displaystyle 2\times 2\)-es négyzet egy fehér kezdetű extra átlóban. Ha pedig a \(\displaystyle d\), \(\displaystyle d+(0,-1)\) és \(\displaystyle d+(1,0)\) mind fekete, akkor \(\displaystyle d+(0,-1)\) és \(\displaystyle d+(1,0)\) alkotják az első fekete mezőkből álló párt egy fekete kezdetű extra átlóban. Például az ábrán egy fehér kezdetű extra átló látható, feltéve hogy a két kérdőjellel jelölt mező közül legalább az egyik fehér.

Az extra átlók lefelé és jobbra haladnak, és felváltva szerepelnek benne \(\displaystyle 2\times 2\)-es fehét négyzetek és átlósan csatlakozó fekete párok. Ha \(\displaystyle \{d,d+(0,-1),d+(1,0),d+(1,-1)\}\) egy fehér \(\displaystyle 2\times 2\)-es négyzet egy \(\displaystyle D\) extra átlóban, akkor az őt követő fekete pár \(\displaystyle \{d+(2,-1),d+(1,-2)\}\). Ha pedig \(\displaystyle \{d+(0,-1),d+(1,0)\}\) egy fekete pár egy \(\displaystyle D\) extra átlóban, akkor azt a \(\displaystyle \{d+(1,-1),d+(1,-2),d+(2,-1),d+(2,-2)\}\) fehér \(\displaystyle 2\times 2\)-es négyzet követi.

Végül minden egyes extra átló fehér végződésű vagy fekete végződésű. Ha \(\displaystyle \{d,d+(0,-1),d+(1,0),d+(1,-1)\}\) egy fehér \(\displaystyle 2\times 2\)-es négyzet, és a \(\displaystyle d+(2,-1)\) és \(\displaystyle d+(1,-2)\) mezők közül legalább az egyik fehér, akkor ez az utolsó fehér \(\displaystyle 2\times 2\)-es négyzet \(\displaystyle D\)-ben, és \(\displaystyle D\) fehér végződésű. Ha pedig \(\displaystyle \{d+(0,-1),d+(1,0)\}\) egy fekete pár \(\displaystyle D\)-ben, és \(\displaystyle d+(1,-1)\) is fekete, akkor ez az utolsó fekete pár \(\displaystyle D\)-ben, és \(\displaystyle D\) fekete végződésű. Például a fenti ábrán látható extra átló fekete végződésű.

Vegyük észre, hogy minden egyes fehér \(\displaystyle 2\times 2\)-es négyzet és minden egyes fekete \(\displaystyle \{d+(0,-1),d+(1,0)\}\) pár egy egyértelmű extra átlóhoz tartozik. Ez is abból a feltételből következik, hogy minden fehér mezőt tartalmaz egy \(\displaystyle 2\times 2\)-es fehér négyzet.

Azt is figyeljük meg, hogy ha egy extra átló fehér végződésű, akkor az utolsó fehér \(\displaystyle 2\times 2\)-es négyzetének a bal felső mezője nincs hozzárendelve semmihez, ha pedig fekete végződésű, akkor az utolsó fekete párt lezáró fekete mező nincs hozzárendelve semmihez.

Azt fogjuk végül megmutatni, hogy extra átlóból legalább annyi van, mint speciális útból. Ha ez megvan, akkor az extra átlóhoz tartozó, a hozzárendelésből kimaradt mezőkből van elég, és ezekből a megfelelő számút rendeljük hozzá a speciális utakhoz.

A stratégiánk most a következő: a speciális utakhoz a tartalék átlók elejének vagy végének valamekkora részét fogjuk hozzárendelni.

Legyen \(\displaystyle c_1c_2c_3\) egy speciális út, és legyen \(\displaystyle c_2=(x,y)\). Ekkor tehát \(\displaystyle c_1=(x-1,y)\) és \(\displaystyle c_3=(x,y+1)\) fehér, \(\displaystyle c_2=(x,y)\) és \(\displaystyle d_2=(x-1,y+1)\) fekete.

Mivel mindegyik fehér mezőt tartalmaz egy \(\displaystyle 2\times 2\)-es fehér négyzet, ezért \(\displaystyle c_1\) egy ilyen négyzet (jelölje \(\displaystyle S_1\)) jobb felső mezője, \(\displaystyle c_3\) pedig egy ilyen négyzet (jelöje \(\displaystyle S_3\)) bal alsó mezője, ahogy ez az alábbi ábrán látható.

\(\displaystyle \begin{matrix} -& -& W& W\\ -& B& W& W\\ W& W& B& -\\ W& W& -& -\\ \end{matrix}\)

Most pedig vizsgáljuk meg a \(\displaystyle d_1=d_2+(-1,0)=(x-2,y+1)\) és \(\displaystyle d_3=d_2+(0,1)=(x-1,y+2)\) mezőket. Négy eset lehetséges:

1. eset: Mindkét mező fekete. Ekkor a \(\displaystyle \{d_1,d_3\}\) párra végződik egy extra átló. Rendeljük hozzá ezt avégződést a \(\displaystyle P\) speciális úthoz.

2. eset: \(\displaystyle d_1\) fehér és \(\displaystyle d_3\) fekete. Ekkor a \(\displaystyle d_1\) mezőt tartalmazza egy \(\displaystyle 2\times 2\)-es \(\displaystyle K_1\) négyzet (ha több is, válasszuk ki az egyiket). Rendeljük hozzá \(\displaystyle K_1\) felét \(\displaystyle P\)-hez. Az is világos, hogy az \(\displaystyle S_1\) négyzet egy extra átló eleje. Rendeljük hozzá \(\displaystyle S_1\) felét is \(\displaystyle P\)-hez.

3. eset: \(\displaystyle d_1\) fekete és \(\displaystyle d_3\) fehér. Ezt az előző esettel analóg módon kezeljük.

4. eset: Mindkét mező fehér. Ekkor a \(\displaystyle d_1\) és a \(\displaystyle d_3\) mezőkhöz lehet találni egy őket tartalmazó \(\displaystyle K_1\), illetve \(\displaystyle K_3\) \(\displaystyle 2\times 2\)-es fehér négyzetet. Ekkor \(\displaystyle K_1\) és \(\displaystyle K_3\) is egy-egy extra átló utolsó fehér négyzete, és rendeljük hozzá mindkét négyzet felét a \(\displaystyle P\) speciális úthoz.

Ezután vizsgáljuk meg az \(\displaystyle e_1=c_2+(0,-1)=(x,y-1)\) és \(\displaystyle e_3=c_2+(1,0)=(x+1,y)\) mezőket. Ismét négy esetet kell megvizsgálni:

1. eset: Mindkét mező fekete. Ekkor az \(\displaystyle \{e_1,e_2\}\) párral kezdődik egy extra átló. Rendeljük hozzá ezt a párt \(\displaystyle P\)-hez.

2. eset: \(\displaystyle e_1\) fehér és \(\displaystyle e_3\) fekete. Az \(\displaystyle e_1\) fehér négyzetet tartalmazza egy \(\displaystyle L_1\) fehér négyzet. Ekkor az \(\displaystyle L_1\) egy extra átló eleje, és a felét rendeljük hozzá \(\displaystyle P\)-hez. Továbbá \(\displaystyle S_1\)-ben végződik egy extra átló, és ennek a felét is rendeljük hozzá \(\displaystyle P\)-hez.

3. eset \(\displaystyle e_1\) fekete és \(\displaystyle e_3\) fehér. Ezt az esetet az előző esettel analóg módon kezeljük.

4. eset: Mindkét mező fehér. Ekkor \(\displaystyle e_1\)-et és \(\displaystyle e_3\)-at is tartalmazza egy-egy fehér \(\displaystyle 2\times 2\)-es \(\displaystyle L_1\) és \(\displaystyle L_3\) négyzet, melyek egy-egy extra átló elejét alkotják. Rendeljük hozzá \(\displaystyle L_1\) és \(\displaystyle L_3\) felét a \(\displaystyle P\) speciális úthoz.

Figyeljük meg a következőket:

(a) minden speciális úthoz hozzárendeltük extra átlók valamekkora részét, melyek összsúlya 2.

(b) A fehér kezdetű extra utak elejének felét legfeljebb két speciális úthoz rendeltük hozzá, és hasonló érvényes a fehér végződésekre is.

Ez nem teljesen nyilvánvaló. Tegyük fel, hogy a \(\displaystyle D\) extra átló a \(\displaystyle \{d,d+(-1,0),d+(0,1),d+(-1,1)\}\) fehér négyzettel kezdődik. Jelölje \(\displaystyle M\) azoknak a speciális utaknak a középső mezőjét, melyekhez az \(\displaystyle D\) kezdetének fele van hozzárendelve. Ekkor nem nehéz ellenőrizni, hogy a \(\displaystyle d+(0,1)\), \(\displaystyle d+(1,1)\) és \(\displaystyle d+(2,0)\) mezők közül legfeljebb egy lehet \(\displaystyle M\)-ben, és hasonló érvényes a \(\displaystyle d+(-1,0)\), \(\displaystyle d+(-1,-1)\) és \(\displaystyle d+(-2,0)\) mezőkre is, más mező pedig nem jön szóba. A fehér végzősek esetén hasonlók mondhatók.

(c) Minden egyes fekete kezdet legfeljebb egy speciális úthoz lett hozzárendelve, és ugyanez igaz a fekete végződésekre is.

(d) Minden egyes extra átlónak egy eleje és egy vége van (definíció szerint ez legyen akkor is így, ha csak egy tagja van az átlónak).

Ezeket összerakva azonnal látszik, hogy speciális útból nem lehet több, mint extra átlóból, és ezzel a bizonyítást befejeztük.

Megjegyzés: \(\displaystyle n^2/2-O(n)\) darab szót el lehet érni, ha minden mezőt befeketítünk, melyekre \(\displaystyle x+y\) osztható néggyel (a táblázat szélén ügyelve rá, hogy teljesüljön a feladat feltétele). Sok más mintával is elérhető, hogy a táblázatban a szósűrűség közel \(\displaystyle 1/2\) legyen. (Itt \(\displaystyle O(n)\) (ejtsd: nagy ordo \(\displaystyle n\)) egy olyan sorozatot jelöl, melyre \(\displaystyle O(n)/n\) korlátos.)

Statisztika:

8 dolgozat érkezett.
7 pontot kapott:	Szakács Ábel, Varga Boldizsár.
2 pontot kapott:	1 versenyző.
1 pontot kapott:	2 versenyző.
0 pontot kapott:	3 versenyző.

A KöMaL 2023. novemberi matematika feladatai