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

[Igor Borovikov]

Это из книги "Digital Geometry" R.Kliette, A.Rosenfeld стр.32.

Уже отчаялся решить, вдруг кто поможет! На языке оригинала:

"Prove that, if all the points in an infinite set are at integer distances from each other, the points must be collinear."

Надо полагать, что это бесконечное множество живет в линейном векторном пространстве. Интересно, что утверждение задачи не верно для некоторых метрик на ЛВП. Оставим неточную формулировку на совести авторов, потому как для Эвклидовой метрики, видимо, это так. Но вот как доказать?

[Igor Borovikov]

Решение случайно нашлось:

http://www.ics.uci.edu/~eppstein/junkya ... ances.html

[maxim5]

Всем привет!
Помогите плиз решить задачу. На плоскости дано конечное множество точек (все не лежат на одной прямой) с условием: если окружность построена на трех точках этого множества, то на ней лежит и четвертая точка этого множества. Доказать, что все точки лежат на одной окружности.
Для решения задачи мне необходимо использовать так называемый экстремальный метод, то есть построить доказательство, опираясь на какое-либо экстремальное свойство. Например, отталкиваясь от минимальной окружности или пары точек с минимальным расстоянием между ними и т.д.
Но было бы интересно посмотреть и на любое другое решение этой задачи.

[Sasha Rybak]

Рассмотри пару (точка; окружность, проходящая через некоторые три точки), такую, что расстояние от точки до окружности - наименьшее из ненулевых.

[maxim5]

А как мне определить наименьшее расстояние от точки до окружности - через касательную или как-то по другому?
Что дает такой подход - не вижу продолжения.

P.S. Если у кого-то есть в "запасе" задачи подобного рода, буду признателен. То есть это задачи типа "дано конечное множество точек на плоскости ..."

[arqady]

maxim5 писал(а):

P.S. Если у кого-то есть в "запасе" задачи подобного рода, буду признателен. То есть это задачи типа "дано конечное множество точек на плоскости ..."

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

2) Дано конечное множество точек на плоскости, никакие три из которых не лежат на одной прямой и такое, что для любых трёх точек из этого множества и для окружности, проходящей через них, существует четвёртая точка из этого множества, лежащая на этой окружности.
Докажите, что все точки данного множества лежат на одной окружности.

Вторая - следствие первой.

[maxim5]

Это очень известные задачи (теорема Сильвестра и следствие из нее). Меня больше интересуют менее классические варианты, может быть где-то на олимпиадах что-нибудь использовалось или в статьях недавних попадалось...
Но все равно спасибо за участие

[Sasha Rybak]

maxim5 писал(а):

А как мне определить наименьшее расстояние от точки до окружности - через касательную или как-то по другому?
Что дает такой подход - не вижу продолжения.

Расстояние от точки A до окружности - это расстояние от точки A до БЛИЖАЙШЕЙ к A точки на данной окружности. Его можно определить так. Проведём из центра окружности луч через точку A. Он пересечёт окружность в некоторой точке B. Расстоянием от точки A до окружности считаем длину отрезка AB.

Что делать дальше? Пусть точки A, B, C, D лежат на одной окружности W, а точка E - некоторая точка, НЕ ЛЕЖАЩАЯ на окружности W. Тогда несложно показать, что в множестве {A, B, C, D} найдутся три точки P1, P2, P3, что расстояние от P3 до окружности, проходящей через P1, P2 и E, будет МЕНЬШЕ, чем расстояние от E до окружности W.
Поэтому ВЫБРАННАЯ окружность (образующая наименьшее ненулевое расстояние с некоторой точкой) может проходить только через ТРИ точки.

arqady писал(а):

2) Дано конечное множество точек на плоскости, никакие три из которых не лежат на одной прямой и такое, что для любых трёх точек из этого множества и для окружности, проходящей через них, существует четвёртая точка из этого множества, лежащая на этой окружности.
Докажите, что все точки данного множества лежат на одной окружности.

Вроде-бы, это и есть задача, упомянутая автором темы. :)

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

[maxim5]

"Тогда несложно показать, что в множестве {A, B, C, D} найдутся три точки P1, P2, P3, что расстояние от P3 до окружности, проходящей через P1, P2 и E, будет МЕНЬШЕ, чем расстояние от E до окружности W."

Для меня это оказалось сложнее, чем Вы предполагали. Прошу ещё раз о помощи.

[Sasha Rybak]

Цитата:

Тогда несложно показать, что в множестве {A, B, C, D} найдутся три точки P1, P2, P3, что расстояние от P3 до окружности, проходящей через P1, P2 и E, будет МЕНЬШЕ, чем расстояние от E до окружности W.

Вот я и вернулся. Напишу решение.
ЛЕММА 1. Пусть V и W - пересекающиеся разные окружности. Пусть A, B - разные точки их пересечения; С, D - разные точки на W, равноудалённые от A и B. Тогда расстояние до окружности V монотонно возрастает на каждой из (меньших) дуг AC, AD, BC и BD окружности W.
-----------
ДОКАЗАТЕЛЬСТВО. Пусть P - центр V, Q - центр W, R - некоторая точка на W. Тогда расстояние от R до V равно $|PR-r_V|=|\sqrt{QP^2+QR^2-2QP \cdot QR \cos \angle PQR}-r_V|$. (Под PR и подобными записями имеются в виду ДЛИНЫ соответствующих отрезков, r_V - радиус окружности V.) Следовательно, на (любой) дуге СD окружности W длина PR изменяется монотонно. Отсюда следует утверждение леммы.

ЛЕММА 2. Пусть V и W - разные окружности. Пусть R - точка на W, S - точка на V, ближайшая к R, T - точка на W, ближайшая к S. Тогда, если R не совпадает с A, B, C, D из ЛЕММЫ 1, то выполняется строгое неравенство ST<RS.
----------
ДОКАЗАТЕЛЬСТВО. Пусть P - центр V, Q - центр W. S - это точка пересечения луча PR c окружностью V, Т - точка пересечения луча QS c W. По выбору точки T (как БЛИЖАЙШЕЙ) возможны лишь варианты ST<RS или ST=RS. Покажем, что второй случай невозможен. Поскольку R не совпадает с A, B, C, D, то T не совпадает c R. А двух ближайших к S точек (на окружности W, естественно) быть не может, если только S не является центром W. Но для точки R, не совпадающей с A, B, C, D, точка S не может являться центром W.

Теперь рассмотрим наше главное утверждение. Пусть F - ближайшая к E точка на W (или одна из ближайших точек). Пусть точки A, B, C, D идут на W именно в таком порядке, причём F лежит на дуге CD (на той из дуг, на которой нет A, B). Рассмотрим окружность V, проходящую через A, B и E.
Пусть M - середина дуги AFB. Пусть Q - центр W. Рассмотрим случай $\angle MQC \ge \angle MQD$ - другой аналогичен. На дуге AMB точки С, F, D лежат именно в таком порядке - поэтому $\angle MQC=\max(\angle MQC,\angle MQD) \ge \angle MQF$. По ЛЕММЕ 1, $d(C,V) \le d(F,V)$ (d(X,Y) - это расстояние между объектами X и Y). По ЛЕММЕ 2, $d(F,V) \le EF=d(E,W)$, причём равенство возможно только если F=M. Но в этом случае имеем $\angle MQC > \angle MQF$, что делает строгим неравенство $d(C,V) \le d(F,V)$.
То есть, $d(C,V) \le d(F,V) \le d(E,W)$, причём хотя бы одно из неравенств - строгое. А значит, d(C,V)<d(E,W), и пара (С,V) будет нужной парой (точка, окружность).

[maxal]

Вот еще такая задачка:

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

[maxim5]

to Sasha Rybak:
Спасибо тебе огромное! Единственное, что хотелось бы сказать, что я не ожидал такого достаточно сложного решения. Это плод твоей работы?

to maxal:
Задача достаточно интересная. Ты её сам можешь решить?

[arqady]

maxal писал(а):

Вот еще такая задачка:

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

Эта задача была на мат-бою между 2- ой и 679 -ой школами Москвы в 1988 или в 1989 году,
закончившимся победой 679 школы!
Придумал её Гриша Кондаков, по-моему.

[neo66]

arqady писал(а):

maxal писал(а):

Вот еще такая задачка:

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

Эта задача была на мат-бою между 2- ой и 679 -ой школами Москвы в 1988 или в 1989 году,
закончившимся победой 679 школы!
Придумал её Гриша Кондаков, по-моему.

Не знаю насчет Гриши , но П.Эрдеш ее придумал несколько раньше - в 1945.
Хадвигер Г., Дебруннер Г. Комбинаторная геометрия плоскости. Наука, 1965, задача 9.

[arqady]

neo66 писал(а):

Не знаю насчет Гриши

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

neo66 писал(а):

но П.Эрдеш ее придумал несколько раньше - в 1945.
Хадвигер Г., Дебруннер Г. Комбинаторная геометрия плоскости. Наука, 1965, задача 9.

Спасибо!