IX CPS - Zadanie 6

Zawody matematyczne:

IX CPS, 2009

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

$ G=\left\{(x,y)\colon x,y\in\{1,2,\dots,n\}\right\}, $

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

$ \begin{split} |\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}=\\ &=\frac{16n^3-4n\sqrt{n}}{8n^2}=2n-\frac{1}{2\sqrt n}>2n-1, \end{split} $

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ż

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

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.