Задача 109783

Темы:    [ Системы точек ] [ Покрытия ] [ Свойства параллельного переноса ] [ Гомотетия помогает решить задачу ]

Сложность: 6 Классы: 10,11

Условие

Авторы: Дольников В.Л., Карасев Р.

На плоскости дано конечное множество точек X и правильный треугольник T . Известно, что любое подмножество X' множества X , состоящее из не более 9 точек, можно покрыть двумя параллельными переносами треугольника T . Докажите, что все множество X можно покрыть двумя параллельными переносами T .

Решение

Нам понадобятся две леммы:

Лемма 1. Если два треугольника T₁ и T₂ гомотетичны с положительным коэффициентом и треугольник T₂ пересекает каждую прямую, содержащую сторону треугольника T₁ , то T₂ содержит T₁ .
Доказательство. Очевидно.

Лемма 2. Для любого конечного множества точек M и треугольника T найдется треугольник T' , гомотетичный T с положительным коэффициентом, содержащий M и содержащий на каждой своей стороне какую-то точку из M .
Доказательство. Рассмотрим какой-то треугольник, положительно гомотетичный T и содержащий M . Если какая-то его сторона не пересекается с M , уменьшим его гомотетией с центром в противоположной этой стороне вершине и добьемся, чтобы сторона пересеклась с M и треугольник все еще содержал M . Повторяя это для каждой стороны, получим требуемое.

Заметим, что в условии предыдущей леммы любой положительно гомотетичный T треугольник, содержащий M , содержит также и T' по лемме 1.

Теперь перейдем к решению задачи. Применим лемму 2 к T и X . Получим треугольник, обозначим его для определенности ABC . На сторонах BC , AC и AB есть соответственно три точки x_A , x_B и x_C из множества X , среди которых могут быть совпадающие.

Если ABC не превосходит T по размерам, доказательство очевидно закончено. Иначе рассмотрим три треугольника AB_AC_A , A_BBC_B и A_CB_CC , положительно гомотетичные ABC с центрами в его вершинах и равные исходному T . Обозначим подмножества множества X

X_A = XΔ AB_AC_A X_B = XΔ A_BBC_B X_C = XΔ A_CB_CC.
Докажем еще одну лемму:

Лемма 3. Если какой-то треугольник T' , получающийся из T параллельным переносом, содержит точки x_A и x_B , то он не может пересекать множество X_C . Аналогично для других пар точек и соответствующего им множества.
Доказательство. Предположим противное. Так как T' содержит x_A и x_B , то одна из этих точек лежит по одну сторону с C относительно A_CB_C , иначе длина стороны T' больше A_CB_C .

Тогда можно заметить, что T' пересекает все прямые сторон A_CB_CC , а значит содержит A_CB_CC . Так как эти треугольники равны, то они совпадают, но тогда T' не может пересекать X_C Лемма доказана.

Теперь применим лемму 2 к треугольнику T и множествам X_A , X_B , X_C , получим треугольники T_A , T_B , T_C , причем на их сторонах можно выбрать точки {x_AB, x_AC, x_A} , {x_BA, x_BC, x_B} , {x_CA, x_CB, x_C} соответственно (некоторые из них могут совпасть), лежащие в соответствующих множествах X_A, X_B, X_C.

К точкам x_A , x_B , x_C , x_AB , x_AC , x_BA , x_BC , x_CA , x_CB применим условие задачи. Они содержатся в треугольниках T₁ и T₂ , являющихся параллельными переносами T .

Какие-то две из первых трех точек содержатся в одном из этих треугольников, без ограничения общности x_A,x_B T₁ . Тогда по лемме 3 треугольник T₁ не пересекает множество X_C и все три точки x_C , x_CA , x_CB содержатся в другом треугольнике T₂ . Отсюда следует, что множество X_C содержится в T₂ по лемме 1; значит, треугольники A_CB_CC и T₂ покрывают все множество X .

Источники и прецеденты использования

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	2003
Этап
Вариант	5
Класс
Класс	10
задача
Номер	03.5.10.4