Вопрос школьника
На плоскости даны п точек (п > 3), никакие три из которых не лежат на одной прямой. Докажите, что существует треугольник с вершинами в данных точках, который не содержит ни одной из остальных (п — 3) точек.
Ответ от учителя
Для доказательства данного утверждения воспользуемся методом индукции.
База индукции: пусть п = 4. Тогда имеется всего 4 точки, никакие три из которых не лежат на одной прямой. Таким образом, любой треугольник, образованный этими точками, не содержит ни одной из оставшихся точек.
Шаг индукции: пусть утверждение верно для п = k (k > 3). Докажем, что оно верно и для п = k + 1.
Рассмотрим множество точек из первых k точек. По предположению индукции, существует треугольник с вершинами в этих точках, который не содержит ни одной из оставшихся (k — 3) точек.
Добавим к этому треугольнику новую точку. Если эта точка лежит внутри треугольника, то мы нашли требуемый треугольник. Если же эта точка лежит вне треугольника, то она образует новый треугольник с двумя вершинами из предыдущего треугольника и одной из новой точки. Этот треугольник также не содержит ни одной из оставшихся точек.
Таким образом, мы доказали утверждение для всех значений п > 3.
