|
|
 |
Условие
В квадрате расположено K точек (K > 2). На какое наименьшее число треугольников нужно разбить квадрат, чтобы в каждом треугольнике находилось не более одной точки?Решение
Данное решение предполагает, что точкам не разрешается лежать на границе квадрата и на границах треугольников. Если же предполагать, что могут, то решение останется тем же, за исключением случая K = 1.Нам потребуется следующая лемма:
Лемма. Пусть в треугольнике ABC расположено k > 0 точек. Тогда треугольник можно разбить на k треугольников так, чтобы в каждом из них находилось ровно по одной точке.
Доказательство леммы. Докажем эту лемму индукцией по k. База k = 1 очевидна: единственным треугольником разбиения будет исходный треугольник. Пусть теперь для всех k < K утверждение верно. Докажем его для k = K. Переобозначив при необходимости вершины треугольника ABC, можно считать, что не все отмеченные точки лежат на прямой, проходящей через вершину A. Тогда через вершину A можно провести прямую l такую, что по каждую сторону от этой прямой есть хотя бы одна отмеченная точка, а на самой прямой ни одной отмеченной точки нет. Эта прямая разбивает треугольник ABC на два треугольника, в каждом из которых лежит не более K - 1 точки. А значит, по предположению индукции каждый этих треугольников можно разбить на треугольники, в каждом из которых будет находиться ровно по одной точке. Суммарное разбиение этих двух треугольников дает разбиение исходного треугольника на K треугольников, удовлетворяющих условию леммы. Утверждение доказано.
Заметим, что если есть всего одна точка, причём расположенная в центре квадрата, то треугольников не менее трех. Если же она расположена не в центре квадрата, то хотя бы одна из двух диагоналей дает искомое разбиение. Докажем, что при K > 1 квадрат можно разбить на K + 1 треугольник. Для этого заметим, что найдётся хотя бы одна из вершин квадрата, для которой не все точки лежат на прямой, проходящей через неё. Пусть это вершина A квадрата ABCD. Тогда существует точка P, лежащая на стороне BC, для которой ни одна из данных в задаче точек не лежит на отрезках AP и DP, а также не все данные точки лежат в одном из треугольников ABP, APD и DCP. Но тогда, применив лемму к каждому из этих треугольников, получим, что существует разбиение на K + 1 треугольник, удовлетворяющее условию задачи.
Теперь докажем, что меньшего числа треугольников не всегда достаточно. Пусть
O — центр данного квадрата ABCD. Расположим K точек на интервале BO.
Предположим, что существует разбиение квадрата на K треугольников,
удовлетворяющее условию задачи. Тогда в каждом треугольнике лежит ровно одна
отмеченная точка и каждая отмеченная точка лежит ровно в одном треугольнике
(то есть точка не может лежать на границе двух треугольников). В этом
разбиение рассмотрим все треугольники с вершиной D. Если таких
треугольников несколько, то хотя бы один из них либо не содержит прямую BD,
либо какая-нибудь из сторон этого треугольника лежит на прямой BD. Ни в
одном из этих случаев в этом треугольнике не может быть отмеченных точек, что
противоречит доказанному. Следовательно, такой треугольник если и может
быть, то только один. Но тогда две его стороны лежат на отрезках AD и CD,
а значит, этот треугольник содержится в треугольнике ACD, тем самым ни одна
отмеченная точка не может лежать в нём. Получили противоречие. Тем самым
доказали, что невозможно удовлетворяющее условию задачи разбиение квадрата
на K треугольников.
