В прямоугольнике 3 см * 4 см расположено 6 точек. Помогите доказать, что найдется пара точек, удаленных одна от другой не более чем $%\sqrt{5}$%

задан 26 Фев '13 11:15

изменен 26 Фев '13 15:15

%D0%A5%D1%8D%D1%88%D0%9A%D0%BE%D0%B4's gravatar image


5525

10|600 символов нужно символов осталось
3

Разбивая прямоугольник, как показано на рисунке, получаем 5 частей, в пределах каждой из которых любые две точки находятся друг от друга не далее, чем на расстоянии $%\sqrt 5.$% Тогда какие либо две точки из данных 6-ти наверняка попадут в одну и ту же часть. Эти точки и образуют нужную пару.

alt text

ссылка

отвечен 26 Фев '13 22:39

Да, такое решение, конечно, намного проще! И "домики" получились красивые! Я как-то изначально не верил в возможность удачного разбиения на $%5$% частей, и искал что-то существенно более сложное.

(26 Фев '13 22:43) falcao
10|600 символов нужно символов осталось
1

В таких задачах обычно разбивают фигуру на части, а затем доказывают, что в какую-то из частей попадёт заданное число точек. Скажем, если бы нам удалось разбить фигуру на $%5$% частей, то по принципу Дирихле оказалось бы, что в одной из "клеток" (частей) сидит по крайней мере два "зайца" (точки). Однако в данной задаче потребуется некоторый дополнительный анализ.

Прежде всего, достаточно "поймать" две из шести точек в прямоугольник размером $%1\times2$% (ориентированный горизонтально или вертикально). При этом расстояние между точками не превосходило бы длины диагонали прямоугольника, которая равна $%\sqrt{5}$%. Поэтому рассуждать будем от противного: мы предположим, что любые две точки удалены друг от друга на расстояние более $%\sqrt{5}$%, и потому в каждом прямоугольнике $%1\times2$% имеется не более одной из шести наших точек.

Рассмотрим произвольное покрытие исходного прямоугольника $%3\times4$% плитками домино. Таких плиток ровно $%6$%, и в каждой из них должно быть ровно по одной точке. Их имеется не более одной, но если их нет совсем, то на пять оставшихся плиток приходится не более пяти точек. Кроме того, никакая точка не может принадлежать сразу двум плиткам, располагаясь на границе, поскольку такие точки мы произвольным образом можем относить к любой из частей. И тогда получится, что в одной из частей точек как бы нет.

Теперь покроем всё горизонтальными плитками, и сторона $%1\times4$% (как снизу, так и сверху) покрыта двумя плитками, то есть точек в этих пределах имеется ровно две. Рассмотрим одну из таких сторон -- это горизонтальная полоса из четырёх клеток. Две наши точки не могут обе располагаться в пределах крайних клеток: тогда на две средние клетки ничего не приходится. Также не может быть так, что ни одна из крайних клеток не содержит точки: на средние клетки их тогда придётся две. Поэтому будем считать, что на нижней стороне точек нет на крайнем слева поле, но точка есть на крайнем поле справа.

Для верхней полосы теперь возможны два случая. Первый: на крайней слева клетке точка есть, на крайней справа -- нет. Тогда мы можем рассмотреть исходный прямоугольник без двух клеток: левой нижней и правой верхней. Он покрывается пятью плитками домино, а точек по-прежнему $%6$%, что приводит к противоречию.

Второй случай заключается в том, когда на крайней слева клетке верхней полосы точек нет, а на крайней справа она есть. Здесь у нас точки есть в клетках справа -- как в самой верхней, так и самой нижней. Нетрудно понять, что те клетки, в которых есть одна из шести точек, будут расположены в "шахматном" порядке. Можно теперь рассмотреть квадрат размером $%3\times3$%, отрезая крайний левый ряд, и в этом квадрате наших точек будет ровно пять.

Рассмотрим центр этого квадрата. Он удалён от его вершин на расстояние $%3\sqrt{2}/2 < \sqrt{5}$%. Это значит, что если бы какая-то из наших пяти точек располагалась в центре, то ни в одной из угловых клеток квадрата ничего располагаться бы уже не могло. Однако наша точка не обязана быть в центре, и при этом она смещена относительно центра в каком-то направлении. Из соображений симметрии, мы можем считать, что она смещена вправо и вверх. Но тогда ясно, что все точки крайнего правого верхнего квадратика $%1\times1$% удалены от этой точки на расстояние меньше $%\sqrt{5}$%, то есть точек в этом квадратике нет, что приводит к противоречию. Значит, наше предположение было неверно, и тем самым найдутся те две точки, которые нам были нужны.

Это рассуждение, скорее всего, можно где-то упростить.

ссылка

отвечен 26 Фев '13 21:00

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×2,924

задан
26 Фев '13 11:15

показан
1371 раз

обновлен
26 Фев '13 22:43

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru