Пусть на листе бумаги осталосьk≥ 1 неразгаданных точекc_k,1,c_k,2, …,c_k,k. Покажем, как с помощью 2k+ 1 попытки разгадать одну из них. Начертим на листе бумаги отрезок прямойl, не пересекающей отмеченный круг. На этом отрезке так укажем (k+ 1) точку a_k,1,a_k,2, …,a_{k,k + 1}, чтоa_k,jлежит строго междуa_{k,j − 1}иa_{k,j + 1}для всехj= 2,3, … ,k. Пусть Миша назвал для этих точек расстоянияd_k,1,d_k,2, … ,d_{k,k + 1}соответственно. Найдём с помощью циркуля и линейки и укажем такие точкиb_k,j(j= 1,2,…,k), что они лежат по ту же сторону от прямойl, что и отмеченный круг, и отстоят от точекa_k,jиa_{k,j + 1}на расстоянияd_k,jиd_{k,j + 1}соответственно (те индексыj, для которых такую точкуb_k,jуказать невозможно, мы пропускаем). Докажем, что среди указанных точекb_k,jнайдётся по крайней мере одна из точекc_k,i(i= 1,2,…,k). Действительно, по принципу Дирихле найдутся по крайней мере две точкиa_k,jиa_k,m(1 ≤j<m≤k+ 1), для которых ближайшей из неразгаданных точек будет одна и та же точкаc_k,iдля некоторогоi(1 ≤i≤k). Тогда, как нетрудно показать, для любой точки из отрезка [a_k,j,a_k,m], и в частности для точкиa_{k,j + 1}, точкаc_k,iтакже будет являться ближайшей из всех неразгаданных точек. Следовательно,c_k,iбудет отстоять от точекa_k,jиa_{k,j + 1}на расстоянияd_k,jиd_{k,j + 1}соответственно, и лежать по ту же сторону от прямойl, что и отмеченный круг. Таким образом, точкаc_k,iсовпадает с одной из указанных нами точекb_k,j(j= 1,2,…,k). Итак, не более чем за 2k+ 1 попытки можно заведомо разгадать одну из неразгаданных точек. Докажем индукцией поn, что действуя указанным выше образом дляk=n,n− 1, …, 1, Коля разгадает все загаданные Мишей точки менее чем за (n+ 1)²попытку. Пустьn= 1, тогда указанный выше способ позволяет угадать единственную неразгаданную точку за 3 < (n+ 1)²попытки. Предположим, чтоNнеразгаданных точек можно заведомо разгадать менее чем за (N+ 1)²попытку. Пусть n=N+ 1. Разгадаем одну из загаданных Мишей точек указанным выше способом не более чем за 2N+ 3 попытки. Тогда по предположению индукции, все точки могут быть разгаданы менее чем за (N+ 1)²+ 2N+ 3 = (N+ 2)²попыток. Утверждение доказано.

Ответ задачи отсутствует