Problem C. 1898. (April 2026)
C. 1898. We would like to select some of the nine lattice points of a \(\displaystyle 2\times 2\) square lattice such that no three of them form a right triangle.
a) Prove that it's not possible to select five points with the property above.
b) How many ways are there to select four points satisfying the above property? (Two selections are considered different if there is a point that is selected in one of them and not selected in the other.)
Proposed by Márton Ujházy, Budapest
(5 pont)
Deadline expired on May 11, 2026.
Sorry, the solution is available only in Hungarian. Google translation
Megoldás. Mindkét feladatrészhez fontos észrevétel, hogy ha egy pont meg van jelölve, akkor nem fordulhat elő, hogy vele egy sorban és vele egy oszlopban egyaránt van egy-egy további megjelölt pont. Ekkor ugyanis a három pont derékszögű háromszöget alkotna.
Ebből következik az is, hogy ha a megjelölt pontok száma legalább 4, akkor nem fordulhat elő olyan sor, amelyben mindhárom pont megjelölt, hiszen a három közül valamelyikkel egy oszlopban biztosan van további pont. Erre az észrevételre a továbbiakban telisor-állításként hivatkozunk.
Térjünk rá az a) rész igazolására. Indirekt bizonyítunk, tegyük fel, hogy jelölhető 5 pont anélkül, hogy kapnánk derékszögű háromszöget. Mivel a pontok száma 5, a skatulyaelv miatt biztosan van olyan sor, amelyben két pont is jelölve van. A megjelölt két ponttal egy oszlopban már nem jelölhetünk további pontot a fenti megjegyzésünk miatt,tehát a maradék három pontot a harmadik oszlopba kell kerülnie. Ez azonban lehetetlen, hiszen a harmadik oszlopban három hely van a maradék három jelölésre, viszont a megkezdettel egy sorba nem lehet elem (telisor-állítás). Ez pedig ellentmondás, hiszen két helyen kellene három pontot megjelölni. Tehát öt pont jelölése a feladatbeli feltétel megtartásával lehetetlen.
A b) rész végiggondolásához jelöljük a sorokat 1-gyel, 2-vel, 3-mal, az oszlopokat A-val, B-vel, C-vel az ábrán látható módon:
Mivel négy pontot kell megjelölnünk, biztosan lesz olyan sor, amelyben van két megjelölt pont. Vizsgáljuk külön az eseteket aszerint, hogy melyik sorban van két megjelölt pont.
Ha van két megjelölt pont az 1-es sorban van, három eset lehetséges aszerint, hogy melyik pont marad jelöletlen.
- Ha a két megjelölt pont az \(\displaystyle A1\) és \(\displaystyle B1\), a maradék két pontnak a \(\displaystyle C\) oszlopban kell lennie. \(\displaystyle C1\) nem lehet jelölve (telisor-állítás), tehát az \(\displaystyle A1\) és \(\displaystyle B1\) pontokon kívül csak \(\displaystyle C2\) és \(\displaystyle C3\) lehet jelölt pont. Ez a négy pont megfelelő pontnégyest alkot.
- Ha a két megjelölt pont az \(\displaystyle A1\) és \(\displaystyle C1\), a maradék két pontnak a \(\displaystyle B\) oszlopban kell lennie. \(\displaystyle B1\) nem lehet jelölve (telisor-állítás), de hasonlóan a \(\displaystyle B2\) sem, mert \(\displaystyle A1, B2, C1\) derékszögű háromszöget alkot. Ez azt jelenti, hogy ebből az esetből nem kaphatunk megfelelő megoldást.
- Ha a két megjelölt pont a \(\displaystyle B1\) és \(\displaystyle C1\), szimmetria miatt az első esethez hasonlóan csak az \(\displaystyle A2\), \(\displaystyle A3\), \(\displaystyle B1\), \(\displaystyle C1\) pontnégyest kaphatjuk.
Azt láttuk tehát, hogy ha van két jelölt pont az 1. sorban, akkor két megfelelő konfiguráció van. Térjünk rá arra az esetre, amikor két jelölt pont van a második sorban van.
- Ha a két megjelölt pont az \(\displaystyle A2\) és \(\displaystyle B2\), a maradék két pontnak a \(\displaystyle C\) oszlopban kell lennie. \(\displaystyle C2\) nem lehet jelölve (telisor-állítás), tehát az \(\displaystyle A2\) és \(\displaystyle B2\) pontokon kívül csak \(\displaystyle C1\) és \(\displaystyle C3\) lehet jelölt pont. Azonban ez sem jó pontnégyes, hiszen \(\displaystyle C1,B2, C3\) derékszögű háromszöget alkot.
- Ha a két megjelölt pont az \(\displaystyle A2\) és \(\displaystyle C2\), a maradék két pontnak a \(\displaystyle B\) oszlopban kell lennie. Ez azonban nem lehetséges, mert az eddig jelöltekkel a \(\displaystyle B1\) és \(\displaystyle B3\) egyaránt derékszögű háromszöget alkot.
- Ha a két megjelölt pontok \(\displaystyle B2\) és \(\displaystyle C2\), az első alesetben látott okok miatt nincs megoldás
Az az eset pedig, amikor van két jelölt pont a 3-mal jelzett sorból, szimmetria miatt lényegében egyezik az első esettel, itt is két megfelelő valósítható meg. Azt is fontos megjegyeznünk, hogy a megtalált pontnégyesek mindegyike különböző, nem kaptunk egyező megoldásokat a különböző esetekből.
Összegezve, a megfelelő pontnégyesek száma \(\displaystyle 2+0+2=4\).
Statistics:
Problem C. 1898. is not processed yet.
Problems in Mathematics of KöMaL, April 2026