Problem B. 4937. (February 2018)

B. 4937. In the plane, a set of lattice quadrilaterals with the following property is selected: however the lattice points are coloured with a finite number of colours, there will always be a selected quadrilateral whose vertices all have the same colour. Prove that there are infinitely many selected lattice quadrilaterals, no two of which have a vertex in common.

Proposed by L. Surányi, Budapest

(6 pont)

Deadline expired on March 12, 2018.

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

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.

Statistics:

43 students sent a solution.
6 points:	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 points:	1 student.
2 points:	2 students.
0 point:	4 students.

Problems in Mathematics of KöMaL, February 2018