Problem B. 5242. (April 2022)

B. 5242. Let \(\displaystyle m\) and \(\displaystyle n\) denote arbitrary positive integers. Consider those lattice points \(\displaystyle (x;y)\) in the Cartesian coordinate plane for which \(\displaystyle 1\le x\le m\) and \(\displaystyle 1\le y\le n\). What is the maximum possible number of points that can be selected out of these \(\displaystyle mn\) lattice points such that no four points selected should form a non-degenerate parallelogram?

Proposed by E. Füredi, Budapest

(6 pont)

Deadline expired on May 10, 2022.

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

Megoldás. A válasz \(\displaystyle m+n-1\).

Konstrukció: válasszuk ki az összes olyan rácspontot a megadott halmazból, amelynek az \(\displaystyle x\) vagy \(\displaystyle y\) koordinátája \(\displaystyle 1\). Ez éppen \(\displaystyle n+m-1\) pont. Ha négyet kiválasztunk közülük, akkor

• vagy lesz közülük három, amelynek ugyanaz a koordinátája 1, ekkor ez a három egy egyenesre esik, tehát nem alkotnak négyszöget;
• vagy az \(\displaystyle (x_1,1),(x_2,1),(1,y_1),(1,y_2)\) pontokat választottuk ki valamilyen \(\displaystyle 1 < x_1 < x_2 \leq m\) és \(\displaystyle 1 < y_1 < y_2 \leq n\) egész számokra. Az ezen négy pont által meghatározott konvex négyszögben az \(\displaystyle (x_1,1)\)-et \(\displaystyle (x_2,1)\)-gyel összekötő szakasz és az \(\displaystyle (y_1,1)\)-et az \(\displaystyle (y_2,1)\)-gyel összekötő szakasz éppen szemközti oldalak (közös csúcsuk nincs és átlók sem lehetnek, mivel nem metszik egymást) és merőlegesek egymásra.

Tehát biztosan nem alkot paralelogrammát ez a négy pont.

Felső korlát: Tegyük fel, hogy valaki legalább \(\displaystyle n+m\) rácspontot kiválasztott a halmazból. Belátjuk, hogy ezek között található négy, amely nem-elfajuló paralelogrammát alkot.

Nevezzük egy sorban levőnek azokat a rácspontokat, amelyek \(\displaystyle y\) koordinátája megegyezik. Színezzük kékre azokat a kiválasztott rácspontokat, amelyek a saját sorukban a legbalrább esnek (legkisebb \(\displaystyle x\) koordinátájúak) a kiválasztottak közül. Az összes többi kiválasztott rácspontot színezzük pirosra. A kék rácspontok száma legfeljebb \(\displaystyle m\) (hiszen \(\displaystyle m\) sor van, és mindegyikben legfeljebb 1 kék lehet), tehát a piros rácspontoké legalább \(\displaystyle n\).

Minden piros rácspont mellé írjuk oda, hogy mennyivel nagyobb az \(\displaystyle x\) koordinátája, mint a sorában szereplő kék rácsponté. Így minden piros rácspont mellé egy \(\displaystyle n\)-nél kisebb pozitív egész számot írunk.

Tehát a skatulyaelv alapján lesz két különböző piros rácspont, amelyek mellé ugyanazt a számot írtuk (és ez a két rácspont nem lehet ugyanabban a sorban). Ekkor ez a két piros rácspont a soraikban levő kék rácspontokkal együtt egy paralelogrammát alkot, hiszen az egy sorban levő párokat összekötő szakaszok egyenlő hosszúak és párhuzamosak (mindegyik ,,vízszintes'', azaz párhuzamos az \(\displaystyle x\) tengellyel).

Statistics:

32 students sent a solution.
6 points:	Balla Álmos András, Bencsik Dávid, Bényei Borisz, Duchon Márton, Fülöp Csilla, Kalocsai Zoltán, Lovas Márton, Melján Dávid Gergő, Mohay Lili Veronika, Móricz Benjámin, Nagy 429 Leila, Németh Márton, Sági Mihály, Somogyi Dalma, Szakács Ábel, Szanyi Attila, Tarján Bernát, Tóth 057 Bálint, Varga Boldizsár, Virág Rudolf, Wiener Anna, Zömbik Barnabás.
5 points:	Bálint Béla, Chrobák Gergő, Csonka Illés, Simon László Bence, Szabó 810 Levente.
4 points:	1 student.
3 points:	1 student.
2 points:	2 students.
0 point:	1 student.

Problems in Mathematics of KöMaL, April 2022