Ёлки и фонари • Константин Кноп, Евгений Епифанов • Научно-популярные задачи на "Элементах" • Математика

Ёлки и фонари

Задача

На большой-пребольшой площади в канун Нового года поставили много-много ёлок и много-много фонарей, причём ёлок было больше, чем фонарей. Может ли оказаться так, что на расстоянии 1 метр от каждой ёлки стоит ровно 8 фонарей? (Ёлки и фонари считаются точками, а площадь — плоской.)


Подсказка 1

Да, так может оказаться.


Подсказка 2

Попробуйте сначала придумать решение для более простого случая: когда на расстоянии 1 м от каждой ёлки находятся по 2 фонаря и ёлок больше, чем фонарей.


Решение

Сначала обсудим более простой случай из подсказки 2. Поместим фонари в квадратную решетку со стороной 2 м, а елки — в середины всех отрезков между двумя соседними фонарями. Если на одной стороне стоит N фонарей, то всего фонарей будет N2. Ёлок при этом будет 2N(N − 1), потому что половина из них стоит на вертикальных отрезках, а половина — на горизонтальных. Уже при N = 3 ёлок будет больше, чем фонарей. На рисунке 1 показана ситуация при N = 5: на площади 25 фонарей и 40 ёлок.

Рис. 1.

В решении основной задачи мы сохраним расположение и фонарей, и почти всех ёлок (те, которые не будут удовлетворять условию, просто уберём с площади). А что тогда можно изменить? Как ни парадоксально, изменить лучше всего единицу измерения, то есть метр. Скоро будет понятно, почему.

Пусть имеется большая площадь, на которой ёлки и фонари стоят так же, как в разобранном выше примере. Сначала ответим вот на какой вопрос: существует ли окружность с центром в заданной ёлке, на которой находятся ровно 8 фонарей? Можем считать, что эта ёлка находится в начале координат, а оси координат идут параллельно отрезкам, соединяющим ближайшие фонари (пусть ось абсцисс идет вдоль того отрезка, на котором стоит наша ёлка). Тогда фонари будут иметь координаты вида (2k + 1, 2l), где k и l — целые числа (единица масштаба — метр, который мы еще не меняли). По теореме Пифагора квадрат расстояния от фонаря с координатами (2k + 1, 2l) до ёлки равен (2k + 1)2 + (2l)2. Такие суммы могут быть равны друг другу для разных пар целых чисел (k, l). Например, 12 + 82 = 72 + 42 = 65. Это значит, что фонари в точках (7, 4) и (1, 8) находятся на равных расстояниях от ёлки. Но тогда на том же расстоянии от нее находятся и фонари, стоящие в точках (−7, 4), (7, −4), (−7, −4), (−1, 8), (1, −8), (−1, −8), и всего таких фонарей будет ровно 8 (на рис. 2 они показаны синим, для наглядности через них проведена окружность). Вообще говоря, мы не доказали, что их не будет больше восьми, но это несложное упражнение оставим читателю для самостоятельного решения.

Рис. 2.

Теперь мы готовы к обещанному "изменению метра". Пусть теперь новым метром станет радиус этой самой окружности, на которой мы нашли 8 фонарей. Тогда для всех ёлок, которые находятся достаточно "глубоко внутри площади" условие про 8 фонарей будет выполнено. Осталось посчитать, что такое "глубоко внутри". Ёлка должна быть такой, чтобы справа и слева от нее на 7 "старых метров" и сверху-снизу на 8 "старых метров" стояли фонари. Сколько таких ёлок на горизонтальных отрезках, если число фонарей вдоль стороны квадрата равно N? Мы должны убрать ёлки верхних и нижних четырех рядов и ёлки из трёх левых и трёх правых середин отрезков. То есть в каждом горизонтальном ряду теперь N − 7 ёлок (а не N − 1, как было раньше), а рядов таких теперь N − 8, а не N. То же самое можно сказать про ёлки на вертикальных рядах, поэтому общее число ёлок равно 2(N − 7)(N − 8). Неравенство 2(N − 7)(N − 8)>N2 выполнено при N ≥ 26 (рис. 3). При таких N условие задачи будет выполнено.

Рис. 3.


Послесловие

Отметим, что в нашем решении использовались идеи, близкие к которым рассматривались в задаче Окружности на клетчатой бумаге. В ней подробно разобрано, как искать на клетчатой плоскости окружности, проходящие через заданное число узлов сетки. Также отметим, что нашу задачу можно решать и по-другому: см. решение задачи М1129 "Задачника "Кванта".

Вообще, задач о конфигурациях конечного числа точек на плоскости, которые бы удовлетворяли определенным свойствам, — великое множество. Кажется, что это всё должны быть "детские" вопросы вроде нашего, но многие такие задачи оказываются очень сложными и ими занимаются профессиональные математики. Раздел математики, посвященный подобным задачам — комбинаторная геометрия, — развивался в течение всего XX века, и большой вклад в этот процесс внес Пол Эрдёш.

Многие задачи комбинаторной геометрии подкупают простотой своих формулировок. Например: доказать, что если не все точки в наборе лежат на одной прямой, то найдется прямая, проходящая ровно через две из этих точек. Это — теорема Сильвестра-Галлаи (Sylvester-Gallai theorem), которая решена уже довольно давно. Но, как и подобает хорошей задаче, из нее вытекают другие вопросы: раз эта теорема утверждает, что обязательно найдется хотя бы одна прямая, проходящая ровно через две точки, то сколько вообще может быть таких прямых? Пару лет назад статью, посвященную этому вопросу, опубликовал Теренс Тао, что лишний раз показывает, что от несложных вопросов до передовых краев науки часто бывает довольно короткий путь.

Автор задачи и решения: Константин Кноп
Автор послесловия: Евгений Епифанов


Понравилась статья? Поделиться с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: