Задачи комбинаторной геометрии

[neo66]

arqady писал(а):

Теперь будете знать!

Буду, если Вы расскажете. Я с ним лично не знаком и даже никогда о нем не слышал. Видимо вследствие присущего мне невежества. Может он, кстати, еще какие-нибудь хорошие задачи придумал? Буду очень рад услышать.

[Юстас]

Sasha Rybak писал(а):

Вот другая задача в тему.
Дано конечное множество точек на плоскости, такое, что любой треугольник в с вершинами из данного множества имеет площадь не более 1. Доказать, что всё множество можно покрыть треугольником площади 4.
(Конечность множества не обязательна, но она упрощает решение.)

Izvinyaus' za translit, no poka pisat po-russki vozmojnosti net.
Eto navernoe samaya prostaya zadacha iz predlojennih v teme. Dostatochno rassmotret' treugolnik max ploshadi i opredelit' GMT, gde mogut lejat drugie tochki mnojestva - eto budet peresechenie treh polos, parallelnih storonam treugolnika. Peresecheniem budet takje treugolnik ploshadi v 4 raza bol'she ishodnogo.

[Sasha Rybak]

maxim5 писал(а):

...я не ожидал такого достаточно сложного решения. Это плод твоей работы?

Да, моей.

Ещё напишу решение последней нерешённой задачи в этом разделе.

maxal писал(а):

На плоскости задано бесконечное число точек так, что все попарные расстояния целочисленны. Доказать, что все эти точки лежат на одной прямой.

Рассмотрим три точки A, B, C, не лежащие на одной прямой. Пусть AB=c, AC=b, BC=a. По условию, a, b, c - натуральные. Покажем, что для ДОСТАТОЧНО ДАЛЁКОЙ точки U все три расстояния UA=x, UB=y, UC=z не могут быть целыми. Поскольку U, A, B, C лежат на одной плоскости, определитель Грама векторов UA, UB, UC равен 0. То есть:
$\begin{vmatrix} (\vec{UA},\vec{UA}) & (\vec{UA},\vec{UB}) & (\vec{UA},\vec{UC}) \\ (\vec{UB},\vec{UA}) & (\vec{UB},\vec{UB}) & (\vec{UB},\vec{UC}) \\ (\vec{UC},\vec{UA}) & (\vec{UC},\vec{UB}) & (\vec{UC},\vec{UC}) \\ \end{vmatrix}=0$.

Отнимем первую строчку от остальных, а в полученной
матрице - первый столбец от остальных:
$0=\begin{vmatrix} (\vec{UA},\vec{UA}) & (\vec{UA},\vec{UB}) & (\vec{UA},\vec{UC}) \\ (\vec{UB},\vec{UA}) & (\vec{UB},\vec{UB}) & (\vec{UB},\vec{UC}) \\ (\vec{UC},\vec{UA}) & (\vec{UC},\vec{UB}) & (\vec{UC},\vec{UC}) \\ \end{vmatrix}= \begin{vmatrix} (\vec{UA},\vec{UA}) & (\vec{UA},\vec{UB}) & (\vec{UA},\vec{UC}) \\ (\vec{UB}-\vec{UA},\vec{UA}) & (\vec{UB}-\vec{UA},\vec{UB}) & (\vec{UB}-\vec{UA},\vec{UC}) \\ (\vec{UC}-\vec{UA},\vec{UA}) & (\vec{UC}-\vec{UA},\vec{UB}) & (\vec{UC}-\vec{UA},\vec{UC}) \\ \end{vmatrix}= \begin{vmatrix} (\vec{UA},\vec{UA}) & (\vec{UA},\vec{UB}-\vec{UA}) & (\vec{UA},\vec{UC}-\vec{UA}) \\ (\vec{UB}-\vec{UA},\vec{UA}) & (\vec{UB}-\vec{UA},\vec{UB}-\vec{UA}) & (\vec{UB}-\vec{UA},\vec{UC}-\vec{UA}) \\ (\vec{UC}-\vec{UA},\vec{UA}) & (\vec{UC}-\vec{UA},\vec{UB}-\vec{UA}) & (\vec{UC}-\vec{UA},\vec{UC}-\vec{UA}) \\ \end{vmatrix}.$
Отметим, что $\vec{UB}-\vec{UA}=\vec{AB},\ \vec{UC}-\vec{UA}=\vec{AC}$, поэтому:
$0=\begin{vmatrix} (\vec{UA},\vec{UA}) & (\vec{UA},\vec{AB}) & (\vec{UA},\vec{AC}) \\ (\vec{AB},\vec{UA}) & (\vec{AB},\vec{AB}) & (\vec{AB},\vec{AC}) \\ (\vec{AC},\vec{UA}) & (\vec{AC},\vec{AB}) & (\vec{AC},\vec{AC}) \\ \end{vmatrix}.$

Воспользуемся формулой для скалярного произведения: $(\vec{KL},\vec{KM})=\frac{|\vec{KM}|^2+|\vec{KL}|^2-|\vec{KM}-\vec{KL}|^2}{2}$, а также учтём, что $(\vec{LK},\vec{KM})=-(\vec{KL},\vec{KM})$. Получаем:
$0=\begin{vmatrix} x^2 & \frac{y^2-x^2-c^2}{2} & \frac{z^2-x^2-b^2}{2} \\ \frac{z^2-x^2-b^2}{2} & c^2 & \frac{b^2+c^2-a^2}{2} \\ \frac{z^2-x^2-b^2}{2} & \frac{b^2+c^2-a^2}{2} & b^2 \\ \end{vmatrix}= \begin{vmatrix} 2x^2 & y^2-x^2-c^2 & z^2-x^2-b^2 \\ z^2-x^2-b^2 & 2c^2 & b^2+c^2-a^2 \\ z^2-x^2-b^2 & b^2+c^2-a^2 & 2b^2 \\ \end{vmatrix}.$
В последнем преобразовании мы умножили каждую строчку на 2. Это не поменяет значение НУЛЕВОГО определителя.

Пусть y=x+e, z=x+d. Подставим это в определитель:
$0=\begin{vmatrix} 2x^2 & 2xe+e^2-c^2 & 2xd+d^2-b^2 \\ 2xe+e^2-c^2 & 2c^2 & b^2+c^2-a^2 \\ 2xd+d^2-b^2 & b^2+c^2-a^2 & 2b^2 \\ \end{vmatrix}= \begin{vmatrix} 2 & 2e+\frac{e^2-c^2}{x} & 2d+\frac{d^2-b^2}{x} \\ 2e+\frac{e^2-c^2}{x} & 2c^2 & b^2+c^2-a^2 \\ 2d+\frac{d^2-b^2}{x} & b^2+c^2-a^2 & 2b^2 \\ \end{vmatrix}.$
В конце мы поделили первую строчку и первый столбик на x, предполагая его достаточно большим - в том числе x>0.

Теперь начинается магия...

По неравенству треугольника: $|e| \le c,\ |d| \le b$. Поэтому, для достаточно больших x, определитель
$0=\begin{vmatrix} 2 & 2e+\frac{e^2-c^2}{x} & 2d+\frac{d^2-b^2}{x} \\ 2e+\frac{e^2-c^2}{x} & 2c^2 & b^2+c^2-a^2 \\ 2d+\frac{d^2-b^2}{x} & b^2+c^2-a^2 & 2b^2 \\ \end{vmatrix}.$
мало отличается от
$\begin{vmatrix} 2 & 2e & 2d \\ 2e & 2c^2 & b^2+c^2-a^2 \\ 2d & b^2+c^2-a^2 & 2b^2 \\ \end{vmatrix}.$
Ввиду целости последнего, для достаточно больших x должно быть:
$\begin{vmatrix} 2 & 2e & 2d \\ 2e & 2c^2 & b^2+c^2-a^2 \\ 2d & b^2+c^2-a^2 & 2b^2 \\ \end{vmatrix}=0.$

Поскольку A, B, C не лежат на одной прямой, то
$\det(G)=\begin{vmatrix} 2c^2 & b^2+c^2-a^2 \\ b^2+c^2-a^2 & 2b^2 \\ \end{vmatrix}>0.$
Это можно проверить непосредственно. А можно заметить, что это учетверённый определитель Грама для неколлинеарных векторов $\vec{AB},\ \vec{AC}$. Поэтому матрица G в последнем определителе невырождена, а значит, найдутся такие $\alpha,\beta$, что:
$\left \{ \begin{array} & \alpha \cdot 2c^2 + \beta (b^2+c^2-a^2)=2e \\ \alpha(b^2+c^2-a^2) + \beta \cdot 2b^2=2d \\ \end{array}.$
В определителе
$0=\begin{vmatrix} 2x^2 & 2xe+e^2-c^2 & 2xd+d^2-b^2 \\ 2xe+e^2-c^2 & 2c^2 & b^2+c^2-a^2 \\ 2xd+d^2-b^2 & b^2+c^2-a^2 & 2b^2 \\ \end{vmatrix}
отнимем от первого столбца второй, умноженный на $\alpha x$ и третий, умноженный на $\beta x$. Затем аналогично отнимем строки. Учитывая принцип выбора $\alpha,\beta$, получаем:
$0=\begin{vmatrix} 2(1-\alpha e-\beta d)x^2-(\alpha(e^2-c^2)+\beta(d^2-b^2))x & 2xe+e^2-c^2 & 2xd+d^2-b^2 \\ e^2-c^2 & 2c^2 & b^2+c^2-a^2 \\ d^2-b^2 & b^2+c^2-a^2 & 2b^2 \\ \end{vmatrix}= \begin{vmatrix} 2(1-\alpha e-\beta d)x^2-2(\alpha(e^2-c^2)+\beta(d^2-b^2))x & e^2-c^2 & d^2-b^2 \\ e^2-c^2 & 2c^2 & b^2+c^2-a^2 \\ d^2-b^2 & b^2+c^2-a^2 & 2b^2 \\ \end{vmatrix}.$

При ФИКСИРОВАННЫХ a, b, c, $\alpha$ и $\beta$ зависят только от d и e. Вычисляя определитель разложением по первой строчке, имеем:
$\begin{vmatrix} 2(1-\alpha e-\beta d)x^2-2(\alpha(e^2-c^2)+\beta(d^2-b^2))x & e^2-c^2 & d^2-b^2 \\ e^2-c^2 & 2c^2 & b^2+c^2-a^2 \\ d^2-b^2 & b^2+c^2-a^2 & 2b^2 \\ \end{vmatrix}= \begin{vmatrix} 2c^2 & b^2+c^2-a^2 \\ b^2+c^2-a^2 & 2b^2 \\ \end{vmatrix}\cdot P_{d,e}(x)+f(d,e)= \det(G) \cdot P_{d,e}(x)+f(d,e).$

Заметим, что d и e пробегают лишь КОНЕЧНОЕ множество значений: $d \in \{-b,\ -b+1,\ ...,\ b\},\ e \in \{-c,\ -c+1,\ ...,\ c\}$. Поэтому $f(d,e)$ - ограничена. Также вспомним, что $\det(G)>0$. Следовательно, для каждой допустимой пары $(d,e)$: или $P_{d,e}(x) \equiv const$, или $\exists x_{d,e}:\ \forall x>x_{d,e}: |G \cdot P_{d,e}(x)+f(d,e)|>0$. Значит, для $x>\max\{x_{d,e}|d \in \{-b, ..., b\},e \in \{-c, ..., c\},P_{d,e}(x) \not \equiv const \}$ возможно лишь $P_{d,e}(x) \equiv const$. Так как $P_{d,e}(x)$ не имеет свободного члена, то в этом случае $P_{d,e}(x) \equiv 0$. Поэтому получаем равенство:
\begin{vmatrix} 0 & e^2-c^2 & d^2-b^2 \\ e^2-c^2 & 2c^2 & b^2+c^2-a^2 \\ d^2-b^2 & b^2+c^2-a^2 & 2b^2 \\ \end{vmatrix}=0.$
Невозможность последнего равенства при $\det(G)>0$ и $\vec v = \begin{pmatrix} e^2-c^2 \\ d^2 - b^2 \\ \end{pmatrix}\ne \vec 0$ можно проверить и непосредственно. Но это трудно. Легче заметить, что последний определитель равен $-(\vec v,\tilde G \vec v)$, где $\tilde G$ - матрица, состоящая из алгебраических дополнений $G:\ \tilde G=\det(G) \cdot G^{-1}$. Но матрица Грама всегда неотрицательно определённая. В случае $\det(G)>0$ она даже положительно определённая, а с ней положительно определена и $\tilde G$. Значит, равенство $-(\vec v,\tilde G \vec v)=0$ возможно лишь когда $\vec v=\vec 0\ \Rightarrow\ |e|=|c|,|d|=|b|$. А это и значит, что точки B и C лежат на прямой UA.

Осталось заметить, что упомянутое в задаче множество не может быть плотным. Поэтому если оно бесконечно, то достаточно далёкая от A, B, C точка в нём найдётся.

Аналогично можно решать и в случае n-мерного пространства.


Интересно, знает ли кто-то "школьное" решение этой задачи хотя бы для плоскости???

[neo66]

Sasha Rybak писал(а):

Интересно, знает ли кто-то "школьное" решение этой задачи хотя бы для плоскости???

Я уже давал ссылку: Хадвигер Г., Дебруннер Г. Комбинаторная геометрия плоскости. Наука, 1965, задача 9.

[TOTAL]

Пусть расстояние между точками A и B (взятыми произвольно) равно N.
Разность расстояний от произвольной точки X до точек A и B соответственно не превосходит N.
Поэтому для какого-то числа M (оно не превосходит N) имеется бесконечно много точек с разностью расстояний до A и B соответственно равной M. Это означает, что бесконечно много точек лежат на гиперболе, т.е. бесконечно много точек лежат в полосе между близкими (скажем, на расстоянии 1) параллельными прямыми.

Выбирая среди этих точек три достаточно удаленные друг от друга, получаем тупоугольный треугольник, длина наибольшей стороны которого, меньше суммы длин двух других сторон, но меньше всего на чуть-чуть. Учитывая, что расстояния между точками целочисленные, заключаем, что треугольник вырожденный, а три его вершины лежат на одной прямой. Две из этих вершин и новая достаточно удаленная точка из полосы тоже лежат одной прямой. И т.д. Имеем бесконечно много точек, лежащих на одной прямой.

Если предположить, что во множестве точек существует точка, не лежащая на той прямой (скажем, она расположена на расстоянии H от этой прямой), то снова, выбирая эту точку и две достаточно удаленные (в сравнении с H) точки на прямой в качестве вершин треугольника, приходим в противоречие с целочисленностью.

[Sasha Rybak]

TOTAL писал(а):

Это означает, что бесконечно много точек лежат на гиперболе.
...
Выбирая среди этих точек три достаточно удаленные друг от друга, получаем тупоугольный треугольник, длина наибольшей стороны которого, меньше суммы длин двух других сторон, но меньше всего на чуть-чуть. Учитывая, что расстояния между точками целочисленные, заключаем, что треугольник вырожденный, а три его вершины лежат на одной прямой.

Ну и всё. Гипербола и прямая ведь не могут иметь больше 2 общих точек.

Поздравляю, TOTAL! Как говорится, ты крут!

[TOTAL]

Sasha Rybak писал(а):

Гипербола и прямая ведь не могут иметь больше 2 общих точек.

Могут иметь много общих точек. При M=N. При M=0.
Ну а с тем, что если 3 точки гиперболы лежат на одной прямой,
то и все остальные точки этой гиперболы лежат на этой же прямой, согласен.

[Macavity]

Ещё одна задача:

На плоскости взято конечное число красных и синих прямых, среди которых нет параллельных, так, что через любую точку пересечения одноцветных прямых проходит прямая другого цвета. Докажите, что все прямые проходят через одну точку.

[Юстас]

Macavity писал(а):

Ещё одна задача:

На плоскости взято конечное число красных и синих прямых, среди которых нет параллельных, так, что через любую точку пересечения одноцветных прямых проходит прямая другого цвета. Докажите, что все прямые проходят через одну точку.

Пусть не все пересекаются в одной точке. Выкинем сначала все красные прямые, потом все черные и посмотрим, в какой конфигурации больше точек пересечения. Пусть, для определенности, среди черных точек попарных пересечений больше - в точности $N$. Тогда через каждую из этих N точек должна проходить красная прямая, и все точки пересечения красных прямых лежит на черных прямых. Из этого в частности следует, что все красные прямые не могут пересекаться в одной точке. Но тогда точек пересечения красных прямых не меньше $2(N-2)$, то есть $2(N-2)\leq N, \ N\leq 4$. Остается рассмотреть только случай, когда черных прямых 3 и они образуют треугольник, этот случай очевидно в условие не вкладывается.

[Sasha Rybak]

Юстас писал(а):

Из этого в частности следует, что все красные прямые не могут пересекаться в одной точке. Но тогда точек пересечения красных прямых не меньше $2(N-2)$...

Откуда такое неравенство? Только из того, что красные прямые не пересекаются в одной точке?? Тогда как быть, например, с таким случаем: 5 синих прямых дают 10 точек пересечения, эти точки разбиваем на пары и покрываем 5 красными прямыми, у которых тоже 10 точек пересечения?

[Юстас]

Ниоткуда оно не следует, и исправить это похоже не получится.

[Macavity]

Macavity писал(а):

Ещё одна задача:

На плоскости взято конечное число красных и синих прямых, среди которых нет параллельных, так, что через любую точку пересечения одноцветных прямых проходит прямая другого цвета. Докажите, что все прямые проходят через одну точку.

Я всё-таки дам ссылку на задачу и её решение. Она из "Кванта"

"Мотороллер не мой, я просто разместил объяву"

См. здесь

[maxal]

maxal в сообщении #73499 писал(а):

На плоскости задано бесконечное число точек так, что все попарные расстояния целочисленны. Доказать, что все эти точки лежат на одной прямой.

В задаче из 14-го выпуска Мат. Просвещения спрашивается, что будет если все попарные расстояния рациональны.

[ИСН]

Тут TOTAL сказал что-то много букв. Возьмём две точки; они задают этакий пучок гипербол, на котором лежат все остальные. Возьмём другие две; все остальные лежат ещё и на пучке гипербол, растущем из этих двух. Но минуточку, два пучка гипербол пересекаются в конечном множестве точек. Э?
(Это я про целочисленные, да.)
А с рациональными расстояниями ничего не будет. Могут запросто не лежать на одной прямой. Вот:
(0,1)
(0,0)
(3/4,0)
(4/3,0)
(5/12,0)
(12/5,0)
ну и дальше как-то так.

[mihailm]

maxal в сообщении #347313 писал(а):

3. А что если все попарные расстояния рациональны?

Совсем простая задача, например:
такая точка $(0,1)$ и точки $(\frac{2n}{n^2-1},0)$, n целое >1

и для красоты (0,0) добавим