Сначала введем несколько определений.
Точку назовем "проверенной", если в нее был сделан ход. Построенные окружности разделим на "использованные" (те, на которых уже найдена точка), "отброшенные" (точку на которой мы не нашли и искать не хотим - такие в алгоритме появятся) и "активные" - все остальные, на которых точка еще не найдена. Непроверенную точку, в которой пересекаются две активные окружности, назовем "двойной", а ту, в которой пересекаются три - "тройной".
Пусть P - число сделанных ходов, R - число неугаданных точек, A - число активных окружностей. В начальный момент R=n, P=A=0.
Алгоритм поведения Коли.
A) Если двойных точек нет - делает ход в любую непроверенную точку, лежащую вне построенных окружностей. Варианты:
A1) попал в загаданную точку: P:=P+1, R:=R-1.
A2) не попал. Построенная окружность объявляется активной. P:=P+1, A:=A+1. Остаемся в ситуации A или переходим в ситуацию B.
B) Двойные точки есть, тройных точек нет. Делаем ход в любую непроверенную точку вне построенных окружностей, расстояния от которой до всех двойных точек различны (это можно сделать, построив все серединные перпендикуляры и выбрав точку, не принадлежащую ни одному из них). Варианты:
B1) попал в загаданную точку: P:=P+1, R:=R-1.
B2) появилась тройная точка (не более одной). Построенная окружность объявляется активной. P:=P+1, A:=A+1. Переходим в ситуацию С.
B3) новых тройных точек не появилось. Построенная окружность объявляется активной. P:=P+1, A:=A+1. Остаемся в ситуации A или B.
C) Есть одна тройная точка. Ходим в нее. Варианты:
C1) попали в загаданную точку. Ровно три окружности объявляются использованными. P:=P+1, A:=A-3, R:=R-1. Переходим в ситуацию A или B.
C2) не попали, новых тройных точек не появилось. Новую окружность объявляем активной. P:=P+1, A:=A+1. Переходим в ситуацию A или B.
C3) не попали, появилась ровно одна тройная точка. Новую окружность объявляем активной. P:=P+1, A:=A+1. Остаемся в ситуации C.
C4) не попали, появилось более одной тройной точки. Новую окружность отбрасываем. P:=P+1. Переходим в ситуацию A или B.
Рассмотрим величину S=P+6*R-2*A+c, где c=0 в ситуациях A или B, и с=1 в ситуации С.
Нетрудно проверить, что эта величина ни при каком ходе не возрастает, а при любом ходе из ситуации A уменьшается по меньшей мере на 1. Далее, очевидно, что в ситуациях A или B выполняется соотношение A<=2R, а в ситуации C: A<=2R+1. Поэтому при R>0 выполняется утверждение S>0.
Первые два хода всегда делаются в ситуации A, поэтому после них S<=6*n-2. В конце игры R=A=c=0, откуда P=S<=6*n-2, что и требовалось доказать.
