Az A. 814. feladat (2021. december)

A. 814. Adott a síkon 666 különböző pont úgy, hogy nem fedhetők le 10 darab egyenessel. Bizonyítandó, hogy ekkor kiválasztható közülük 66 pont úgy, hogy már azok sem fedhetők le 10 darab egyenessel.

Javasolta: Hujter Mihály (Budapest)

(7 pont)

A beküldési határidő 2022. január 10-én LEJÁRT.

Megoldás. Tegyük föl indirekten, hogy tetszőleges \(\displaystyle 66\) pontra van \(\displaystyle 10\) egyenes, melyekre illeszkednek, de nincs \(\displaystyle 10\) olyan egyenes, melyeken az összes pont rajta van.

Vegyünk \(\displaystyle 66\) tetszőlegesen kiválasztott pontot, ezek lefedhetők \(\displaystyle 10\) egyenessel. Mivel nem lehet minden pont rajta ezeken az egyeneseken, ezért választhatunk egy \(\displaystyle A_1\) pontot, amely nincs rajta ezen a \(\displaystyle 10\) egyenesen. Legyen a \(\displaystyle 10\) egyenes \(\displaystyle ax+by+c=0\) alakú egyenleteinek szorzata \(\displaystyle p_1(x,y)=0\). Most vegyünk \(\displaystyle 66\) pontot, amelyek közt ott van \(\displaystyle A_1\), ezeket is lefedi \(\displaystyle 10\) egyenes. Ezeken sem lehet rajta az összes pont, így választhatunk egy \(\displaystyle A_2\) pontot, amely nincs rajta ezeken az egyeneseken. Ezen egyenesek egyenleteinek szorzatát jelölje \(\displaystyle p_2(x,y)\).

Így tovább, ha már meghatároztuk az \(\displaystyle A_1,A_2,\ldots ,A_k\) pontokat (\(\displaystyle k<66\)), akkor veszünk \(\displaystyle 10\) egyenest, amelyek lefedik őket, azok egyenletienek szorzatát nevezzük \(\displaystyle p_{k+1}(x,y)\)-nak, és választunk egy \(\displaystyle A_{k+1}\) pontot, amely nincs rajta a \(\displaystyle 10\) egyenesen. Végül az \(\displaystyle A_1,A_2, \ldots , A_{66}\) pontokra is illesztünk \(\displaystyle 10\) egyenest, és ezek egyenleteinek szorzatát nevezzük el \(\displaystyle p_{67}(x,y)\)-nak.

Most belátjuk, hogy a \(\displaystyle p_1, p_2,\ldots, p_{67}\) polinomok lineárisan függetlenek. Tegyük föl, hogy a \(\displaystyle c_1,c_2,\ldots,c_{67}\) valós értékekre \(\displaystyle c_1p_1(x,y)+c_2p_2(x,y)+\ldots +c_{67}p_{67}(x,y)\) a konstans \(\displaystyle 0\) polinom. Az \(\displaystyle A_1\) pont koordinátáiban \(\displaystyle p_1\) kivételével az összes polinom értéke \(\displaystyle 0\), \(\displaystyle p_1\) értéke viszont nem \(\displaystyle 0\), így az összegként kapott polinom értéke csak akkor lehet \(\displaystyle 0\) az \(\displaystyle A_1\) pontban, ha \(\displaystyle c_1=0\). Ezután teljes indukcióval bizonyítjuk, hogy minden \(\displaystyle k\le 66\)-ra \(\displaystyle c_k=0\):

Az indukciós feltevés alapján \(\displaystyle c_1, c_2, \ldots , c_{k-1}=0\), az \(\displaystyle A_k\) pontban minden \(\displaystyle j>k\)-ra \(\displaystyle p_j\) értéke \(\displaystyle 0\), és \(\displaystyle j<k\)-ra pedig \(\displaystyle c_jp_j\) értéke \(\displaystyle 0\), tehát az összeg csak akkor lehet \(\displaystyle 0\) az \(\displaystyle A_k\) pontban, ha \(\displaystyle c_kp_k(A_k)=0\), de \(\displaystyle p_k(A_k)\ne 0\), így \(\displaystyle c_k=0\). Tehát \(\displaystyle c_1,c_2,\ldots ,c_{66}=0\), vagyis \(\displaystyle c_{67}p_{67}(x,y)\) a konstans \(\displaystyle 0\) polinom, ami csak úgy lehetséges, ha \(\displaystyle c_{67}=0\). Ezzel tehát bebizonyítottuk, hogy a \(\displaystyle p_1, p_2,\ldots,p_{67}\) polinomok lineárisan függetlenek.

Másrészt az összes \(\displaystyle p_k(x,y)\) polinom \(\displaystyle 10\)-ed fokú kétváltozós polinom, így minden monomjuk \(\displaystyle x^ry^s\) alakú, ahol \(\displaystyle r,s\ge 0\) és \(\displaystyle r+s\le 10\). Ilyen monomból \(\displaystyle \binom{12}{2}=66\) van, tehát a \(\displaystyle 10\)-ed fokú kétváltozós polinomok egy \(\displaystyle 66\) dimenziós vektorteret alkotnak a valós számok fölött. Így nem lehetséges, hogy legyen \(\displaystyle 67\) darab lineárisan független \(\displaystyle p_k\) polinom, azaz ellentmondásra jutottunk.

Statisztika:

4 dolgozat érkezett.
4 pontot kapott:	1 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	2 versenyző.

A KöMaL 2021. decemberi matematika feladatai