A B. 5251. feladat (2022. május)

B. 5251. Vegyük fel azt az \(\displaystyle ABCD\) téglalapot a koordinátarendszerben, amelynek csúcsai \(\displaystyle A(0,0)\), \(\displaystyle B(2022,0)\), \(\displaystyle C(2022,2)\), \(\displaystyle D(0,2)\). Tekintsük azokat az egységnyi területű háromszögeket, amelyek mindhárom csúcsa a téglalap hosszabbik oldalpárjának egy-egy rácspontja. Ezeket a háromszögeket szeretnénk megszínezni úgy, hogy azonos színű háromszögeknek nem lehet közös belső pontjuk. Legalább hány színre van ehhez szükségünk?

Javasolta: Nagy Zoltán Lóránt (Budapest)

(5 pont)

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

Megoldás. A feladatot általánosabban, \(\displaystyle 2022 \times 2\) helyett \(\displaystyle n \times 2\) méretű (\(\displaystyle n > 2\) egész) téglalapra oldjuk meg. Jelöljük a hosszú oldalak rácspontjait a következő módon: \(\displaystyle A_i=(i,0)\), \(\displaystyle D_i=(i,2)\), ahol (\(\displaystyle i=0, \ldots, n\)).

Ha egy háromszög mindhárom csúcsa a téglalap hosszabbik oldalpárjának egy-egy rácspontja, akkor lehet \(\displaystyle A_iA_jD_k\) vagy \(\displaystyle D_iD_jA_k\) típusú (itt \(\displaystyle 0 \leq i < j \leq n\) és \(\displaystyle 0 \leq k \leq n\)). Egy ilyen háromszög vízszintes (\(\displaystyle x\)-tengely irányú) oldalának hossza \(\displaystyle j-i\), míg az erre merőleges magasságvonala \(\displaystyle 2\) egység hosszú, tehát a területe: \(\displaystyle T = \frac{(j-i) \cdot 2}{2} = j-i\). Következésképpen az egységnyi területű, azaz színezésre váró háromszögek éppen az \(\displaystyle A_iA_{i+1}D_k\) és a \(\displaystyle D_iD_{i+1}A_k\) típusú háromszögek minden olyan \(\displaystyle (i,k)\) rendezett párra, amelyben \(\displaystyle i \in \{0,1,\ldots,n-1\}\) és \(\displaystyle k \in \{0,1,\ldots,n\}\). Ez összesen \(\displaystyle n(n-1)\) darab háromszög.

Rögzített \(\displaystyle k\) esetén az \(\displaystyle A_0A_1D_k\), \(\displaystyle A_1A_2D_k\), \(\displaystyle \ldots\) \(\displaystyle A_{n-1}A_nD_k\) háromszögeknek nincsen közös belső pontja, így színezhetők ugyanazzal a színnel.

Hasonlóképpen a \(\displaystyle D_0D_1A_k\), \(\displaystyle D_1D_2A_k\), \(\displaystyle \ldots\) \(\displaystyle D_{n-1}D_nA_k\) háromszögek is lehetnek ugyanolyan színűek. Így a háromszögeket összesen \(\displaystyle 2(n+1)\) háromszög-családra osztottuk (egyenként \(\displaystyle n\) darab háromszöggel), melyek egy-egy színnel kiszínezhetők, tehát \(\displaystyle 2(n+1)\) színnel ki tudjuk színezni a háromszögeket a feladat feltételei szerint.

Sőt, vegyük még észre, hogy az \(\displaystyle A_0\) közös csúcsú és a \(\displaystyle D_n\) közös csúcsú család színezhető ugyanazzal színnel:

Persze az \(\displaystyle A_n\) közös csúcsú és a \(\displaystyle D_0\) közös csúcsú család is lehet azonos színű. Így már \(\displaystyle 2n\) színnel ki tudtuk színezni az összes háromszöget.

Belátjuk, hogy ennél kevesebb szín nem elég. Ehhez elegendő mutatnunk \(\displaystyle 2n\) darab háromszöget, melyek közül bármely kettőnek van közös belső pontja (azaz különböző színt igényelnek).

Ha megvizsgáljuk az \(\displaystyle A_{i} A_{i+1} D_{n-i}\) és a \(\displaystyle D_{i}D_{i+1} A_{n-i}\) háromszögeket minden \(\displaystyle i \in \{0,1,\ldots,n-1\}\) esetén, akkor éppen egy ilyen háromszög-családot kapunk.

Tekintsük ugyanis az \(\displaystyle E = \left(\frac{n}2,1 \right)\) és \(\displaystyle F = \left(\frac{n+1}2,1 \right)\) pontokat. Az \(\displaystyle A_iD_{n-i}\) (és így persze \(\displaystyle D_iA_{n-i}\)) szakaszok felezőpontja \(\displaystyle E\), míg az \(\displaystyle A_{i+1} D_{n-i}\) (és így persze \(\displaystyle D_{i+1}A_{n-i}\)) szakaszok felezőpontja \(\displaystyle F\) minden \(\displaystyle i \in \{0,1,\ldots,n-1\}\) esetén. Tehát a felsorolt háromszögek mindegyikének vízszintes középvonala az \(\displaystyle EF\) szakasz. Következésképpen az \(\displaystyle EF\) szakasz bármely belső pontjára teljesül, hogy az összes vizsgált háromszögnek közös pontja. (Ez még kicsivel erősebb is a kívántnál: nekünk elég lett volna, ha bármely kettőnek van közös pontja, de az derült ki, hogy vannak olyan pontok, amelyek mind a \(\displaystyle 2n\) darab háromszögnek közös pontjai.)

Összefoglalva: általában legalább \(\displaystyle 2n\) színre, speciálisan \(\displaystyle n=2022\) esetén legalább \(\displaystyle 4044\) színre van szükségünk a feltéteket teljesítő színezéshez.

Megjegyzés. Tekintsük azt a \(\displaystyle G_n\) gráfot, amelynek csúcsai a feladatban vizsgált háromszögek. Két csúcsot akkor kötünk össze éllel, ha a nekik megfelelő háromszögeknek van közös belső pontja. A feladat ennek a gráfnak a kromatikus számát (a szokásos jelöléssel: \(\displaystyle \chi(G_n)\)) kérdezi.

A megoldás első felében megmutattuk, hogy \(\displaystyle 2n\) szín elég, azaz \(\displaystyle \chi(G_n) \leq 2n\).

A megoldás második felében pedig megadtunk egy \(\displaystyle 2n\)-csúcsú teljes részgráfot \(\displaystyle G_n\)-ben, azaz beláttuk, hogy \(\displaystyle \omega(G_n) \geq 2n\). (Hagyományosan \(\displaystyle \omega(G)\)-vel jelöljük egy gráf legnagyobb teljes részgráfjának csúcsszámát.)

Triviálisan teljesül minden gráfra, hogy \(\displaystyle \omega (G) \leq \chi(G)\), ezért így kiderült, hogy a \(\displaystyle G_n\) gráfban:

\(\displaystyle \chi(G_n) = \omega(G_n) = 2n. \)

Érdemes azonban tudatosítani, hogy azzal ,,szerencsénk volt'', hogy a vizsgált gráfunkban \(\displaystyle \chi\) és \(\displaystyle \omega\) egyenlő. Ez csak a gráfok kis részére teljesül. Hogy \(\displaystyle G_n\) éppen ilyen, az tette lehetővé, hogy viszonylag egyszerűen tudjunk éles alsó korlátot adni a szükséges színek számára.

Statisztika:

42 dolgozat érkezett.
5 pontot kapott:	Bencsik Dávid, Bényei Borisz, Christ Miranda Anna, Chrobák Gergő, Csilling Dániel, Csonka Illés, Czanik Pál, Dienes Ervin Fotisz, Domján Olivér, Duchon Márton, Fülöp Csilla, Guthy Gábor, Jánosik Máté, Kalocsai Zoltán, Kovács Benedek Noel, Lovas Márton, Melján Dávid Gergő, Mohay Lili Veronika, Móricz Benjámin, Nádor Artúr, Nagy 429 Leila, Nguyen Kim Dorka, Romaniuc Albert-Iulian, Simon László Bence, Somogyi Dalma, Szabó 810 Levente, Tarján Bernát, Tóth 057 Bálint, Varga Boldizsár, Virág Rudolf, Wiener Anna, Zömbik Barnabás.
4 pontot kapott:	Bálint Béla, Tusnády Sámuel.
3 pontot kapott:	3 versenyző.
0 pontot kapott:	5 versenyző.

A KöMaL 2022. májusi matematika feladatai