ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 78609
Темы:    [ Разрезания на части, обладающие специальными свойствами ]
[ Индукция в геометрии ]
[ Прямоугольники и квадраты. Признаки и свойства ]
[ Принцип Дирихле (конечное число точек, прямых и т. д.) ]
Сложность: 4+
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

В квадрате расположено 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 треугольников.

Ответ

3, если k = 1, k + 1 треугольник, если k > 1.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 30
Год 1967
вариант
1
Класс 10
Тур 1
задача
Номер 1

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .