Всего лишь точки

Все мы привыкли, что на чертеже постоянно возникают базовые фигуры геометрии – о тех же треугольнике и квадрате придумано и решено невероятное множество задач. Но в этот раз в нашей задаче окажется еще более базовое понятие – расставлять, перемещать и анализировать мы будем всего лишь точки! Впрочем, и треугольники, и квадраты нам неизбежно встретятся.

В далеком 1972 году Г.А. Гальперин опубликовал в популярном научном журнале «Квант» такую задачу: какое наибольшее число точек можно разместить на плоскости так, чтобы ни один из треугольников с вершинами в этих точках не был тупоугольным? Разумеется, никакие три точки не должны лежать на одной прямой – иначе окажется, что число точек может быть сколь угодно большим. Читателям предлагалось присылать свои решения задачи в редакцию – попробуем свои силы и мы!

Как говорится, главный инструмент математика – это предположение: предположим, что нам уже удалось разместить на плоскости точки А₁, А₂, … А_n, которые удовлетворяют условию задачи. Выберем любые две из них – А_i и A_j. Тогда все оставшиеся точки – обозначим их В – должны принадлежать такому множеству, что отрезки, соединяющие принадлежащие ему точки с выбранными А_i и A_j, не образуют с тупых углов с отрезком А_iA_j. Проще это условие можно записать: для всех точек В верно, что углы ВА_iA_j  и  ВА_jA_i  меньше 90˚. Давайте попробуем представить себе это множество:

Заданные неравенства выполняются только для точек внутри и на границе полосы, перпендикулярной отрезку и по ширине равной его длине. Обозначим эту полосу П(i-j), как соответствующую двум выбранным нами в начале точками.

Выпуклой оболочкой множества точек А₁, А₂, … А_n называется наименьший выпуклый многоугольник, содержащий все эти точки. Так как поставленные нами условия-неравенства должны выполняться для всех пар точек, то получается, что выпуклая оболочка полностью содержится в полосе П(i-j) для любых i и j. А теперь задумайтесь: может ли при таких ограничениях какая-нибудь из точек лежать внутри выпуклой оболочки? Посмотрите:

Если существует хотя бы одна точка В внутри выпуклой оболочки, то условие «выпуклая оболочка лежит внутри всех полос» не выполняется. Мы получили, что все наши точки А₁, А₂, … А_n лежат на границе выпуклой оболочки, то есть представляют собой вершины выпуклого многоугольника – точки не могут быть расположены на его сторонах, ведь никакие три из них не лежат на одной прямой. Это самое важное открытие для решения этой задачи! Осталось всего лишь немного арифметики.

Как известно, сумма углов любого выпуклого n-угольника равна 180*(n-2). При этом нам необходимо, чтобы эти углы не превышали 90˚. Тогда их сумма не превышает 90*n. Получаем неравенство 180*(n-2) ≤ 90*n. Отсюда следует, что число точек не может быть больше четырех.

Очевидно, что для точек-вершин квадрата условие задачи выполняется. Таким образом, мы привели пример для числа точек, равного 4, и доказали, что для большего числа условие неверно. Задача решена! Кстати, если она показалась вам слишком легкой, попробуйте решить ее вторую часть, также опубликованную в журнале «Квант» – найдите число таких точек не для плоскости, а для пространства. Говорят, в редакцию не было прислано не одного полного доказательства!