 |
A B. 5242. feladat (2022. április) |
B. 5242. Legyenek \(\displaystyle m\) és \(\displaystyle n\) tetszőleges pozitív egész számok. Tekintsük azon \(\displaystyle (x;y)\) rácspontokat a derékszögű koordinátarendszerben, amelyekre \(\displaystyle 1\le x\le m\) és \(\displaystyle 1\le y\le n\) teljesül. Legfeljebb hányat választhatunk ki ezen \(\displaystyle mn\) darab rácspont közül úgy, hogy semelyik négy kiválasztott pont se alkosson nem elfajuló paralelogrammát?
Javasolta: Füredi Erik (Budapest)
(6 pont)
A beküldési határidő 2022. május 10-én LEJÁRT.
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).
Statisztika:
32 dolgozat érkezett. 6 pontot kapott: 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 pontot kapott: Bálint Béla, Chrobák Gergő, Csonka Illés, Simon László Bence, Szabó 810 Levente. 4 pontot kapott: 1 versenyző. 3 pontot kapott: 1 versenyző. 2 pontot kapott: 2 versenyző. 0 pontot kapott: 1 versenyző.
A KöMaL 2022. áprilisi matematika feladatai