4
1

Встретил сегодня одну любопытную олимпиадную задачу. Она сравнительно недавняя: её лет 5 назад предложил кто-то из японцев.

Условие звучит так: на плоскости дано 10 точек, расположенных совершенно произвольно. В нашем распоряжении имеется 10 одинаковых монет (например, пятирублёвых). Требуется расположить монеты так, чтобы все 10 точек оказались ими покрыты, а монеты при этом не перекрывались.

Добавление. Решение задачи привёл @Urt. Помещаю ссылку на ту заметку, из которой я узнал об этой задаче.

А вот -- более новая ссылка, которую я нашёл только что. Там предыдущие оценки улучшены.

задан 9 Май '13 0:42

изменен 12 Май '13 1:40

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

Решение Пусть $% R^2 $% – плоскость, $% r()$% – метрика в $% R^2 $%, радиус монет примем за 1, покрываемые точки обозначим $% x_1, x_2,…,x_{10} \in R^2. $% Под областью расположения точек будем понимать множество $% X=\lbrace x \in R^2| $% для некоторого $% j: r(x ,x_j) \le 1 \rbrace . $% На часть плоскости, включающую область X, нанесем гексоидальную разметку с радиусом $% 2 / \sqrt 3 $% (упакованные на плоскости правильные шестиугольники с длиной стороны, равной $% 2/\sqrt 3 $%). В каждый такой шестиугольник впишем круг радиуса 1. Покажем, что существует такой сдвиг разметки, при котором все точки $% x_1, x_2,…,x_{10} $% попадут в какой-нибудь круг. Такое расположение разметки будет соответствовать решению задачи. $%$%
Чтобы это показать, нанесем на область X квадратную (для простоты) $% \epsilon-сеть $% и осуществим по этой сети сдвиги исходной разметки так, чтобы центральная точка шестиугольника не выходила в результате сдвига за пределы этого шестиугольника в исходном состоянии (такие сдвиги далее называем допустимыми). Обозначим: s – площадь квадратной ячейки, N – число допустимых сдвигов, $% I_{ij}\in \lbrace 0,1 \rbrace $% - индикатор не попадания i-й точки в какой-либо единичный круг при j-м сдвиге решетки, $%I_i = \sum_{j} I_{ij}, S= 2 \sqrt 3 $% – площадь шестиугольника, $%\pi $% – площадь круга, $% S- \pi = S_0. $% Для полного множества всех допустимых сдвигов число непопаданий какой-либо точки в единичный круг равно $% N_0=N(I_1=1 \vee I_2=1,…, \vee I_{10}=1) \le \sum_{i} I_{i} =10 I_1. $% Учитывая, что $% lim_{\epsilon \to 0 } \sum_j I_{1j}s =S_0< S/10 $% и $% lim_{\epsilon \to 0 } Ns =S, $% можно подобрать такое значение $% \epsilon, $% для которого $% \sum_{i} I_i /N < 1/10 $% и, следовательно, $% N_0< N. $%

ссылка

отвечен 11 Май '13 23:55

изменен 12 Май '13 1:44

1

Да, идея именно такая, то есть всё следует из неравенства $%\frac{\pi}{2\sqrt{3}} > 1-1/10$%. Известно рассуждение для 12 точек, но оно более сложное. Для очень мелкой сетки ответ будет отрицательный -- там что-то типа 50 с чем-то получается, а что между этими числами -- не известно. Я постараюсь найти ссылку на соответствующую заметку и добавлю её в текст вопроса. P.S. Длина стороны шестиугольника равна $%2/\sqrt{3}$%.

(12 Май '13 1:20) falcao

@Falcao, спасибо за пояснение и указание на опечатку. С ними уже устал бороться - размножаются, какая-то безысходность. Эту никогда не нашел бы.

(12 Май '13 1:38) Urt

@Urt: поскольку там у Вас площадь найдена верно, то на длину можно было даже не обратить внимание. Это всё как в знаменитом высказывание Дьердя Пойя: "He writes a, he says b, he means c, but it should be d." (c) :) Я сейчас нашёл ещё одну более новую заметку по тому же вопросу, и ссылку добавил в текст.

(12 Май '13 1:46) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×832

задан
9 Май '13 0:42

показан
1587 раз

обновлен
12 Май '13 1:46

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

по почте:

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

по RSS:

Ответы

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

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