IX CPS - Zadanie 6

Dana jest liczba całkowita $ n\geq 16 $. Rozważmy zbiór

\[<br /> G=\left\{(x,y)\colon x,y\in\{1,2,\dots,n\}\right\},<br /> \]

składający się z $ n^2 $ punktów płaszczyzny. Niech $ A $ będzie dowolnym podzbiorem $ G $, zawierającym co najmniej $ 4n\sqrt{n} $ punktów. Udowodnić, że istnieje co najmniej $ n^2 $ czworokątów wypukłych, o wierzchołkach w zbiorze $ A $, takich że przekątne każdego z nich przechodzą przez jeden ustalony punkt płaszczyzny.

Rozwiązanie

Niech $ |A|=m\geq4n\sqrt{n} $ i niech $ \mathcal S $ będzie zbiorem wszystkich odcinków o obu końcach w zbiorze $ A $. Wtedy $ |\mathcal S|=\binom m2 $ i obie współrzędne środka dowolnego odcinka z $ \mathcal S $ są naturalnymi wielokrotnościami $ 1/2 $. W kwadracie $ \{(x,y)\colon 1\leq x\leq n, 1\leq y\leq n\} $ jest mniej niż $ 4n^2 $ punktów o współrzędnych będących naturalnymi wielokrotnościami $ 1/2 $, zatem na mocy zasady szufladkowej istnieje punkt $ X $, który jest środkiem przynajmniej $ \binom m2/(4n^2) $ odcinków ze zbioru $ \mathcal S $. Niech $ \mathcal P $ będzie zbiorem wszystkich odcinków z $ \mathcal S $, których środkiem jest $ X $. Wtedy

\[<br /> \begin{split}<br /> |\mathcal P|&\geq\frac{\binom m2}{4n^2}=\frac{m(m-1)}{8n^2}\geq\frac{4n\sqrt{n}(4n\sqrt{n}-1)}{8n^2}=\\<br /> &=\frac{16n^3-4n\sqrt{n}}{8n^2}=2n-\frac{1}{2\sqrt n}>2n-1,<br /> \end{split}<br /> \]

czyli $ |\mathcal P|\geq2n $.

Podzielmy $ \mathcal P $ na rozłączne rodziny odcinków zawartych w tej samej prostej. Załóżmy, że tych rodzin jest $ k $ oraz $ i $-ta rodzina liczy $ a_i $ odcinków, dla $ i=1,\dots,k $. Każdy odcinek z $ a_i $ ma końce należące do $ G $ i środek $ X $, więc $ a_i\leq n/2 $. Ponadto każde dwa odcinki z $ \mathcal P $ są przekątnymi równoległoboku wtedy i tylko wtedy, gdy nie leżą na tej samej linii. Z tego wynika, że liczba różnych równoległoboków o przekątnych ze zbioru $ \mathcal P $ jest nie mniejsza niż

\[<br /> \begin{split}<br /> \sum_{i=1}^{k-1}\sum_{j=i+1}^k a_i a_j &=<br /> \frac12\left(\left(\sum_{i=1}^ka_i\right)^2-\sum_{i=1}^ka_i^2\right)\geq \\<br /> \geq\frac12\left(\left(\sum_{i=1}^ka_i\right)^2-\sum_{i=1}^ka_i\cdot\frac n2\right)<br /> &= \frac12\left(|\mathcal P|^2-|\mathcal P|\cdot\frac n2\right)=\\<br /> =\frac12|\mathcal P|\left(|\mathcal P|-\frac n2\right)&\geq n\left(2n-\frac n2\right)=\frac32n^2>n^2.<br /> \end{split}<br /> \]

Zatem istnieje więcej niż $ n^2 $ czworokątów wypukłych (równoległoboków) spełniających warunki zadania.

Uwaga: Stosując nieco dokładniejsze oszacowania, można udowodnić tezę zadania wymagając dodatkowo, by współrzędne wspólnego punktu $ X $ były liczbami naturalnymi.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź