Задача 86123
|
|
 |
Условие
На прямоугольном листе бумаги нарисован круг, внутри которого Миша мысленно выбирает n точек, а Коля пытается их разгадать. За одну попытку Коля указывает на листе (внутри или вне круга) одну точку, а Миша сообщает Коле расстояние от нее до ближайшей неразгаданной точки. Если оно оказывается нулевым, то после этого указанная точка считается разгаданной. Коля умеет отмечать на листе точки, откладывать расстояния и производить построения циркулем и линейкой. Может ли Коля наверняка разгадать все выбранные точки менее, чем за (n+1)2 попыток?Решение
Пусть на листе бумаги осталось k ≥ 1 неразгаданных точек ck,1, ck,2, …, ck,k. Покажем, как с помощью 2k + 1 попытки разгадать одну из них.Начертим на листе бумаги отрезок прямой l, не пересекающей отмеченный круг. На этом отрезке так укажем (k + 1) точку
ak,1, ak,2, …, ak,k + 1, что ak,j лежит строго между ak,j − 1 и ak,j + 1 для всех j = 2,3, … , k. Пусть Миша назвал для этих точек расстояния dk,1, dk,2, … , dk,k + 1 соответственно.
Найдём с помощью циркуля и линейки и укажем такие точки bk,j (j = 1,2,…,k), что они лежат по ту же сторону от прямой l, что и отмеченный круг, и отстоят от точек ak,j и ak,j + 1 на расстояния dk,j и dk,j + 1 соответственно (те индексы j, для которых такую точку bk,j указать невозможно, мы пропускаем).
Докажем, что среди указанных точек bk,j найдётся по крайней мере одна из точек ck,i (i = 1,2,…,k). Действительно, по принципу Дирихле найдутся по крайней мере две точки ak,j и ak,m (1 ≤ j < m ≤ k + 1), для которых ближайшей из неразгаданных точек будет одна и та же точка ck,i для некоторого i (1 ≤ i ≤ k). Тогда, как нетрудно показать, для любой точки из отрезка [ak,j, ak,m], и в частности для точки ak,j + 1, точка ck,i также будет являться ближайшей из всех неразгаданных точек. Следовательно, ck,i будет отстоять от точек ak,j и ak,j + 1 на расстояния dk,j и dk,j + 1 соответственно, и лежать по ту же сторону от прямой l, что и отмеченный круг. Таким образом, точка ck,i совпадает с одной из указанных нами точек bk,j (j = 1,2,…,k). Итак, не более чем за 2k + 1 попытки можно заведомо разгадать одну из неразгаданных точек.
Докажем индукцией по n, что действуя указанным выше образом для k = n, n − 1, …, 1, Коля разгадает все загаданные Мишей точки менее чем за (n + 1)2 попытку. Пусть n = 1, тогда указанный выше способ позволяет угадать единственную неразгаданную точку за
3 < (n + 1)2 попытки. Предположим, что N неразгаданных точек можно заведомо разгадать менее чем за (N + 1)2 попытку. Пусть
n = N + 1. Разгадаем одну из загаданных Мишей точек указанным выше способом не более чем за 2N + 3 попытки. Тогда по предположению индукции, все точки могут быть разгаданы менее чем за (N + 1)2 + 2N + 3 = (N + 2)2 попыток. Утверждение доказано.
