Problem B. 5251. (May 2022)

B. 5251. The vertices of a rectangle \(\displaystyle ABCD\) in the coordinate plane are \(\displaystyle A(0,0)\), \(\displaystyle B(2022,0)\), \(\displaystyle C(2022,2)\), \(\displaystyle D(0,2)\). Consider those triangles of unit area that have all three vertices at lattice points lying on the longer sides of the rectangle. These triangles are to be coloured so that no triangles of the same colour have an interior point in common. What is the minimum number of colours needed?

Proposed by Z. L. Nagy Budapest

(5 pont)

Deadline expired on June 10, 2022.

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

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.

Statistics:

42 students sent a solution.
5 points:	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 points:	Bálint Béla, Tusnády Sámuel.
3 points:	3 students.
0 point:	5 students.

Problems in Mathematics of KöMaL, May 2022