 |
Az A. 783. feladat (2020. október) |
A. 783. Poliminónak nevezünk egy összefüggő alakzatot, ha azt egységnégyzetek oldalaik mentén történő összeillesztésével kapjuk. Legyen \(\displaystyle n\ge 3\) egész szám. Keressük meg \(\displaystyle n\) függvényében a legnagyobb pozitív egész \(\displaystyle C\)-t, melyre teljesül a következő feltétel: ha egy végtelen négyzetrács minden mezőjét kiszínezzük \(\displaystyle n\) szín valamelyikével, akkor található egy legalább \(\displaystyle c\) területű poliminó, mely legfeljebb \(\displaystyle n-1\) színt tartalmaz.
Javasolta: Nikolai Beluhov (Stara Zagora) és Stefan Gerdjikov (Szófia)
(7 pont)
A beküldési határidő 2020. november 10-én LEJÁRT.
Megoldás. A végtelen négyzetrács akármilyen színezésében megkereshető a lehető legnagyobb területű poliminó, melyben valamelyik szín nem fordul elő.
Létezik olyan színezés, melyben ez az érték éppen
\(\displaystyle 2+4+\dots+2(n-1)+\dots+4+2=n(n-1)+(n-1)(n-2)=2(n-1)^2,\)
az alábbi módon. Az \(\displaystyle y=0\) egyenesen az \(\displaystyle x=0,1,2,\dots,2n-1\)-hez tartozó négyzeteken következzék mind az \(\displaystyle n\) szín kétszer, majd mindkét irányban ismételjük ezt a periódust. Az \(\displaystyle y=0\)-ról \(\displaystyle y=1\)-re lépve, cseréljük meg az \(\displaystyle x\)-edik és \(\displaystyle (x+1)\)-edik négyzet színét minden páratlan \(\displaystyle x\)-re. Az \(\displaystyle y=1\)-ről az \(\displaystyle y=2\)-re lépve, a páros \(\displaystyle x\)-eknél cseréljünk, és így tovább, váltogatva. Álljunk meg az \(\displaystyle y=n-1\) egyenesnél, ugyanis egymás mellé kerül az \(\displaystyle (1,0)\) és \(\displaystyle (2n,0)\) négyzetek színe, és a többi (vízszintesen \(\displaystyle 2\)-t lépve, ugyanazt a mintát látjuk). Ezt az eljárást alkalmazva terjesszük ki mindkét \(\displaystyle y\) irányban a színezést a végtelen négyzetrácsra. Világos, hogy bármely színre az ahhoz tartozó négyzetek \(\displaystyle 2(n-1)^2\) területű összefüggő részeket határolnak körül.
Belátjuk, hogy akárhogyan színezzük a végtelen négyzetrácsot, mindenképpen található egy legalább \(\displaystyle 2(n-1)^2\) területű poliminó, melyben valamelyik szín nem fordul elő.
Mérjük meg egy poliminó "kerületét" a következő különleges módon. A poliminó külső határát vizsgáljuk (amit képezhetünk úgy, hogy vesszük minden sorra és oszlopra a két szélső négyzetének szélét). Rajzoljunk a külső határ mindegyik szakaszára kifelé egy \(\displaystyle 1/4\) területű háromszöget, és szomszédos határmezők esetén még egy-egy háromszöget, az alábbi példákat követve:
Eredmény. Ha egy \(\displaystyle P\) poliminó területe \(\displaystyle t=t(P)\) és "kerülete" \(\displaystyle k=k(P)\), akkor \(\displaystyle t\le \frac12(k^2+1)\).
Indoklás. Módosítsuk \(\displaystyle P\)-t úgy, hogy közben \(\displaystyle t(P)\) ne csökkenjék és \(\displaystyle k(P)\) ne növekedjék: elegendő az állítást a végül kapott poliminóra ellenőrizni. Először is, vegyük \(\displaystyle P\)-be az általa körülhatárolt négyzeteket. Másodszor pedig, amíg \(\displaystyle P\) határa mentén előfordul az alábbi három határszakasz egyike, toldjunk oda egy négyzetet, az ábrázolt módon:
E háromféle lépés a "kerületet" megtartja, míg a területet \(\displaystyle 1\)-gyel növeli. Mivel a terület nem nőhet minden határon túl (a "kerület" legalább akkora, mint az alakzat szélességének negyede), ezért eljutunk egy olyan \(\displaystyle P'\) poliminóhoz, ami nem tartalmaz ilyen határszakaszt. Milyen határa lehet akkor?
A határ menti négyzeteket körüljárva, ha "fel-jobb" irányban lépünk, azután csak "fel-jobb" irányban léphetünk, vagy "fel" irányban, de ha "fel" felé léptünk, onnan csak "fel-bal" irányban folytathatjuk, vagy "bal" irányban, de ha "bal" felé léptünk, váltunk, stb. Tehát átlósan haladva kell körbeérnünk, esetleg egy-egy lépést kivéve mindegyik irányban.
Végül, ha "jobb" és "bal" felé is léptünk, szétvághatjuk a poliminót a "jobb" felé lépés felezőmerőlegesén és \(\displaystyle 1\)-gyel arrébb csúsztatva kiegészíthetjük:
Ezt téve feltehető, hogy "jobb" felé, és hasonlóképp "fel" felé sem lépünk. Kétféle poliminó maradt: egy \(\displaystyle a\times b\)-s ferde rács, vagy egy \(\displaystyle a\times b\)-s ferde rács kiegészítve \(\displaystyle (a-1)\) négyzettel. Alább láthatók ezek \(\displaystyle a=4\), \(\displaystyle b=2\) esetén:
Előbbi esetben \(\displaystyle k=a+b\) és \(\displaystyle t=ab+(a-1)(b-1)=2(a-\frac12)(b-\frac12)+\frac12\). Utóbbi esetben \(\displaystyle k=a+b+\frac12\) és \(\displaystyle t=ab+(a-1)(b-1)+(a-1)=2(a-\frac12)b\). Ha adott két szám összege, akkor legnagyobb a szorzatuk, ha különbségük minimális. Ennek jegyében \(\displaystyle 2t\le k^2+1\) leolvasható. \(\displaystyle \blacksquare\)
Vizsgáljunk most egy \(\displaystyle N\times N\) méretű négyzetrácsot a színezésből. Skatulya-elv miatt valamelyik szín legfeljebb \(\displaystyle \frac1n N^2\)-szer fordul elő. Hagyjuk ki azt a színt, és a megmaradó összefüggő részeket jelölje \(\displaystyle P_1,\dots,P_d\). Világos, hogy
\(\displaystyle \sum_{i=1}^d t(P_i)\ge (1-\frac1n)N^2.\)
Ha \(\displaystyle P_1,\dots,P_d\)-hez még hozzávesszük a "kerületüket", nem lesz köztük átfedés! Mivel az így bővített poliminók együtt lefedhetők egy \(\displaystyle (N+1)^2\) területű négyzettel, kapjuk, hogy
\(\displaystyle \sum_{i=1}^d t(P_i)+k(P_i) \le (N+1)^2.\)
Eredményünk rendezésével \(\displaystyle \frac kt \ge \frac{\sqrt{2t-1}}t\) látható. Az \(\displaystyle u=\sqrt{2t-1}\) helyettesítéssel ellenőrizhető, hogy \(\displaystyle t\)-ben szigorú monoton csökkenő a jobb oldal. Ezért ha \(\displaystyle T=\max \{t(P_1),\dots,t(P_d)\}\), akkor
\(\displaystyle (N+1)^2\ge \sum_{i=1}^d t(P_i)\left(1+\frac{k(P_i)}{t(P_i)}\right)\ge \)
\(\displaystyle \ge \sum_{i=1}^d t(P_i)\left(1+\frac{\sqrt{2T-1}}{T}\right)\ge \left(1+\frac{\sqrt{2T-1}}{T}\right)(1-\frac1n)N^2.\)
Hogyha \(\displaystyle T\le 2(n-1)^2-1\), akkor \(\displaystyle \left(1+\frac{\sqrt{2T-1}}{T}\right)(1-\frac1n)>1\) áll fenn \(\displaystyle n\ge 3\) esetén. Ez elegendően nagy \(\displaystyle N\) esetén ellentmondásos, ezért a végtelen négyzetrácsban található legalább \(\displaystyle 2(n-1)^2\) területű poliminó, melyben valamelyik szín nem fordul elő.
Mindez igazolja, hogy a keresett \(\displaystyle C\) érték \(\displaystyle C=2(n-1)^2\).
Megjegyzés. Hasonló gondolatot alkalmaz ez az amerikai versenyfeladat.
Statisztika:
6 dolgozat érkezett. 6 pontot kapott: Füredi Erik Benjámin. 3 pontot kapott: 1 versenyző. 2 pontot kapott: 3 versenyző. 0 pontot kapott: 1 versenyző.
A KöMaL 2020. októberi matematika feladatai