Az A. 833. feladat (2022. október)

A. 833. A koordináta-rendszer néhány rácspontját kiszínezzük pirosra, a többit fehérre. Egy ilyen színezést végesen univerzálisnak nevezünk, ha tetszőleges véges, nemüres \(\displaystyle A \subset \mathbb{Z}\) esetén létezik olyan \(\displaystyle k\in \mathbb{Z}\), hogy az \(\displaystyle (x,k)\) pont pontosan akkor van pirosra színezve, ha \(\displaystyle x\in A\).

\(\displaystyle a)\) Létezik-e olyan végesen univerzális színezés, hogy minden sorban véges sok rácspontot színezünk pirosra, és minden sort különbözőképpen színezünk meg, továbbá a pirosra színezett rácspontok halmaza összefüggő?

\(\displaystyle b)\) Létezik-e olyan végesen univerzális színezés, hogy minden sorban véges sok rácspontot színezünk pirosra, továbbá a pirosra és a fehérre színezett rácspontok halmaza is összefüggő?

A rácspontok egy \(\displaystyle H\) részhalmazát akkor nevezünk összefüggőnek, ha bármely \(\displaystyle x,y\in H\)-ra létezik egy olyan rácsvonalakon haladó út, amely csak \(\displaystyle H\)-beli pontokon megy át, és \(\displaystyle x\)-et összeköti \(\displaystyle y\)-nal.

Javasolta: Kocsis Anett (Budapest)

(7 pont)

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

a) Létezik ilyen színezés.

Gondoljuk meg, hogy fel lehet sorolni az összes olyan lehetséges színezését egy sornak, amiben véges sok piros rácspont van. Ez egy ismert állítás, a következőn múlik: Minden \(\displaystyle k\)-ra könnyű felsorolni az olyan színezéseket, amik pontosan \(\displaystyle k\) darab piros mezőt tartalmaznak (mondjuk a piros mezők koordinátáinak abszolút értékeinek összege szerint növekvő sorrendben, és ahol egyenlőség van ott tetszőlegesen döntünk, hogy ki kerül előbbre). Legyen minden \(\displaystyle k\)-ra ez a felsorolás \(\displaystyle a^k_1, a_k^2, \ldots\). Ezután ezeket "összefésüljük" valahogy, például így:

\(\displaystyle a^1_1, a^2_1, a^1_2, a^3_1, a^2_2, a^1_3, a^4_1, \ldots\)

Tehát (átbetűzve) legyen \(\displaystyle b_1, b_2, \ldots\) az összes lehetséges színezése egy sornak, amiben csak véges sok piros mező szerepel. Továbbá soroljuk fel a páros számokat is a következő módon:

\(\displaystyle 0,2,-2,4,-4,6,-6, \ldots\)

Csináljuk a következő algoritmust: minden lépésben vegyük a következő \(\displaystyle x\) páros számot a felsorolásban, és a következő \(\displaystyle b_i\)-t, amit még nem használtunk. Színezzük meg az \(\displaystyle x.\) sort \(\displaystyle b_i\) szerint. Ezek után, ha \(\displaystyle x>0\), akkor színezzük meg az \(\displaystyle (x-1).\) sort úgy, hogy összefüggővé tegyük a most megszínezett sort az eddig megszínezettekkel, ezt könnyű megcsinálni, színezzünk meg elég sok (de véges) egymást követő mezőt az \(\displaystyle (x-1).\) sorban pirosra úgy, hogy összekapcsolja az \(\displaystyle x.\) és \(\displaystyle (x-2).\) sort. Még arra figyeljünk, hogy az \(\displaystyle (x-1).\) sort olyanra színezzük, amit még nem használtunk, de ez könnyen elérhető a sorban néhány további mező pirosra színezésével, mivel eddig csak véges sok sort színeztünk meg. Ha \(\displaystyle x<0\), akkor hasonlóan, csak akkor az \(\displaystyle (x+1).\) sort kell a fent leírt módon megszínezni, hogy az új sort összekapcsolja a korábban megszínezettekkel.

Világos az algoritmusból, hogy végül egy összefüggő színezést kapunk, nem lesz két azonos sor, és minden sor sorra kerül valamikor, ahol csak véges sok piros van, azaz éppen ilyet szerettünk volna.

b) Itt is létezik konstrukció. Hasonlóan soroljunk fel minden véges pirosat tartalmazó színezést, ahol van legalább egy piros, megint legyenek \(\displaystyle b_0, b_1, \ldots \) és legyen \(\displaystyle b_0\) az a sor, amiben csak a 0 a piros. Most a \(\displaystyle b_i\)-t a \(\displaystyle 100i.\) sorba fogjuk berakni (\(\displaystyle 100\) egyáltalán nem lényeges, sokkal kisebb konstans is elég, csak így szemléletesebb). Színezzük a teljes alsó félsíkot fehérre, ezzel a csupa fehér sor már biztosan szerepel. Indukcióval haladunk. Az első lépés egyszerű, a 0. sorba lerakjuk \(\displaystyle b_0\)-t. Ezek után tegyük fel, hogy már leraktuk \(\displaystyle b_n\)-t a \(\displaystyle 100n.\) sorba úgy, hogy eddig összefüggő a piros rész, és a fehér rész is. Ezek után fedjük le egy hatalmas téglalappal az összes eddig pirosra színezett mezőt úgy, hogy a kerületen se legyenek piros pontok, és a téglalap teteje a \(\displaystyle (100n+50)\). sorban van. Vezessen fel egy egy sávos vékony piros út ideáig. Ez garantálja majd a pirosak összefüggőségét, illevte emiatt világos, hogy a fehérek is összefüggők lesznek, mert mindenhonnan ki lehet jutni a fehér téglalap határára. A \(\displaystyle (100n+50)\)-től \(\displaystyle (100n+99).\) sorig vegyünk olyan sorokat, amikben elég sok szomszédos tag piros, de a csak ezek, tehát egy blokkban vannak, hogy nehogy fehéreket elkerítsünk. A \(\displaystyle (100n+99).\) sorban legyen olyan sok piros, hogy ahogy a \(\displaystyle (100n+100).\) sorba lerakjuk \(\displaystyle b_{n+1}\)-t összefüggőek legyenek a pirosak. Világos a konstrukcióból, hogy ekkor a fehérek is összefüggőek. Végül még azt kell meggondolni, de ez is látható, hogy ekkor a végén is összefüggőek lesznek a pirosak és fehérek is, így kaptunk egy megfelelő végesen univerzális színezést.

Feladat kitűzőinek megjegyzése: Kicsit szerencsétlenül lett megfogalmazva ez a feladat, ráadásul nem sikerült úgy kitűzni, ahogy akartuk. Ebbe a részbe is bele akartuk érteni azt a feltételt, hogy minden sor különbözőképpen van színezve. Erre is írunk egy megoldást:

Ezt nem lehet megcsinálni. Indirekten tegyük fel, hogy van ilyen színezés. Van egy sor, ahol csak a \(\displaystyle 0\) van megszínezve, feltehető, hogy ez a \(\displaystyle 0.\) sor. Keresünk egy végtelen hosszú utat, ami a \(\displaystyle (0,0)\) pontból indul, csak piros rácspontokon megy át, és végig az \(\displaystyle \{(x,y): y>0\}\) felső félsíkon halad, illetve egy ugyanilyet amely végig az \(\displaystyle \{(x,y): y<0\}\) alsó félsíkon halad. Ha találunk ilyet, akkor ezeket az origóban összefűzve egy olyan utat kapunk, amely mindkét irányba végtelen hosszú, és kettévágja a síkot, így például az \(\displaystyle (1,0)\) és \(\displaystyle (-1,0)\) pontokat nem lehet összekötni fehér úttal, ami ellentmondás.

Elég a felső síkra konstruálni egy végtelen hosszú utat, az alsó hasonló módon megy. A \(\displaystyle (0,0)\) pontból minden felső félsíkon lévő piros pontot elérhetünk egy úttal (ami nem metszi önmagát), mivel a piros pontok összefüggőek. Az is világos, hogy minden ilyen útnál végig a felső félsíkon maradunk, mivel a \(\displaystyle 0.\) sorban csak a \(\displaystyle 0\) van megszínezve. Végtelen sok piros pont van a felső félsíkon, így ezzel kaptunk végtelen sok (véges hosszú) utat. Most ezek segítségével gyártunk egy végtelen hosszú utat.

Az első lépés minden úton fel. Mivel végtelen sok út van, és a második lépés csak 3-féle lehet (fel, jobbra, balra) így lesz egy olyan 2. lépés, ami végtelen sok útban szerepel. Válasszuk ezt a 2. lépést, és a többi utat, ahol nem erre lépünk, felejtsük el. Ismételjük ugyanezt: a harmadik lépés legfeljebb 3-féle lehet, így van végtelen sok út, amin ugyanaz, fixáljuk ezt a 3. lépést, és az ettől eltérő utakat hagyjuk el. Továbbra is marad végtelen sok út, aminek az első három lépése egyezik a lefixált lépésekkel. Így tovább, minden \(\displaystyle n\)-re találunk egy \(\displaystyle n.\) lépést. Tehát végül ezzel a lépéssorozattal kapunk egy végtelen hosszú piros utat, éppen ahogy szerettük volna. Ezzel a bizonyítást befejeztük.

Statisztika:

23 dolgozat érkezett.
7 pontot kapott:	Czanik Pál, Diaconescu Tashi, Farkas 005 Bendegúz, Molnár-Szabó Vilmos, Nádor Benedek, Németh Márton, Seres-Szabó Márton, Simon László Bence, Szakács Ábel, Tarján Bernát, Wiener Anna.
6 pontot kapott:	Lovas Márton, Móricz Benjámin.
4 pontot kapott:	4 versenyző.
3 pontot kapott:	2 versenyző.
2 pontot kapott:	2 versenyző.
1 pontot kapott:	2 versenyző.

A KöMaL 2022. októberi matematika feladatai