A B. 4937. feladat (2018. február)

B. 4937. A síkon kiválasztunk rácsnégyszögeket úgy, hogy igaz rájuk a következő: akárhogy színezzük a rácspontokat véges sok színnel, mindig van olyan kiválasztott négyszög, amelynek minden csúcsa ugyanolyan színű. Bizonyítsuk be, hogy van végtelen sok olyan kiválasztott négyszög, amelyek közül semelyik kettőnek nincs közös csúcsa.

Javasolta: Surányi László (Budapest)

(6 pont)

A beküldési határidő 2018. március 12-én LEJÁRT.

Megoldás. Az \(\displaystyle n\geq 1\) számra vonatkozó teljes indukcióval belátjuk, hogy ha már kiválasztottunk \(\displaystyle n\) darab négyszöget (a megadott négyszögek közül), \(\displaystyle N_1\)-et, \(\displaystyle N_2\)-t, ..., \(\displaystyle N_n\)-t, úgy, hogy közülük semelyik kettőnek nincs közös csúcsa, akkor létezik a megadott négyszögek között olyan \(\displaystyle N_{n+1}\) négyszög, amelynek az \(\displaystyle N_1,N_2,\dots,N_n\) négyszögek közül semelyikkel nincs közös csúcsa.

Ha ezt sikerül igazolnunk, akkor készen vagyunk, hiszen egyesével mindig hozzávehetünk az eddig kiválasztott négyszögekhez egy újabbat, melynek nincs velük közös csúcsa, így ezt a végtelenségig folytatva páronként csúcsdiszjunkt négyszögek egy megfelelő végtelen halmazát kapjuk.

Az indukció kezdőlépésénél, \(\displaystyle n=1\) esetén válasszunk ki egyet (tetszőleges módon) a megadott négyszögek közül.

Az indukciós lépés igazolásához tegyük fel, hogy valamely \(\displaystyle n\)-re már találtunk megfelelő \(\displaystyle N_1,N_2,\dots,N_n\) négyszögeket. Ezeknek együttesen \(\displaystyle 4n\) csúcsa van, színezzük ki ezt a \(\displaystyle 4n\) csúcsot \(\displaystyle 4n\) különböző színnel, a többi rácspontot pedig egy újabb, \(\displaystyle 4n+1\)-edik színnel. A feltétel szerint kell lennie olyan \(\displaystyle N_{n+1}\) négyszögnek, amelynek csúcsai egyforma színűek. Ez a közös szín csak a \(\displaystyle 4n+1\)-edik szín lehet, vagyis \(\displaystyle N_{n+1}\)-nek valóban nincs közös csúcsa \(\displaystyle N_1,N_2,\dots,N_n\) egyikével sem.

Ezzel a feladat állítását igazoltuk.

Statisztika:

43 dolgozat érkezett.
6 pontot kapott:	Beke Csongor, Biczó Benedek, Busa 423 Máté, Daróczi Sándor, Dobák Dániel, Döbröntei Dávid Bence, Fitos Bence, Fleiner Zsigmond, Fuisz Gábor, Gáspár Attila, Győrffi Ádám György, Győrffy Ágoston, Hervay Bence, Janzer Orsolya Lili, Kántor András Imre, Kerekes Anna, Molnár Bálint, Molnár-Sáska Zoltán, Nagy Nándor, Nguyen Bich Diep, Pituk Gábor, Póta Balázs, Schifferer András, Schrettner Jakab, Shuborno Das, Soós 314 Máté, Surján Anett, Szabó 417 Dávid, Szabó 864 Blanka, Szabó 991 Kornél, Szabó 997 Balázs István, Terjék András József, Tóth 827 Balázs, Várkonyi Zsombor, Weisz Máté, Zsigri Bálint.
3 pontot kapott:	1 versenyző.
2 pontot kapott:	2 versenyző.
0 pontot kapott:	4 versenyző.

A KöMaL 2018. februári matematika feladatai