Разделы 
Дополнительно
Задача по математике - 3450
2019-06-03 
На прямоугольном листе бумаги нарисован круг, внутри которого Миша мысленно выбирает $n$ точек, а Коля пытается их разгадать. За одну попытку Коля указывает на листе (внутри или вне круга) одну точку, а Миша сообщает Коле расстояние от нее до ближайшей неразгаданной точки. Если оно оказывается нулевым, то после этого указанная точка считается разгаданной. Коля умеет отмечать на листе точки, откладывать расстояния и производить построения циркулем и линейкой. Может ли Коля наверняка разгадать все выбранные точки менее, чем за $(n + 1)^2$ попыток?
Решение:
Покажем сначала, как за $2n+1$ попытку отгадать одну точку. Пусть прямая $l$ не пересекает круг из условия задачи, проведем отрезок этой прямой и отметим на нем $n+1$ точку $X_0, \cdots , X_n$. Узнаем для каждой из них расстояние до ближайшей загаданной точки. По принципу Дирихле , хотя бы для двух (скажем, $X_i$ и $X_{j,i} < j$) из отмеченных $n + 1$ точек Миша назовет расстояние до одной и той же неизвестной нам загаданной точки $Y$.
Лемма. Для всех k таких, что $i < k < j$, Миша также назовет расстояние до точки $Y$.
Доказательство. Пусть $\omega_i$ и $\omega_j$ - окружности с центрами в точках $X_i$ и $X_j$ соответственно, проходящие через точку $Y$. Пусть $Y^{ \prime}$ - вторая точка пересечения этих окружностей (случай касающихся окружностей мы оставляем читателю). Пусть $\omega$ - окружность с центром в точке $X_k$, проходящая через точки $Y$ и $Y^{ \prime}$ (рис.). Достаточно доказать, что окружность $\omega$ содержится внутри объединения кругов, ограниченных окружностями $\omega_i$ и $\omega_j$.
Заметим сначала, что $\omega$ пересекает $\omega_i$ и $\omega_j$ только в точках $Y$ и $Y^{ \prime}$ (так как окружности пересекаются не более чем в двух точках). Значит, каждая из дуг, на которые окружность разбивается точками $Y$ и $Y^{ \prime}$, либо лежит целиком внутри объединения кругов, либо целиком снаружи. Чтобы доказать, что второй случай невозможен, достаточно проверить, что точки пересечения $\omega$ и прямой $l$ лежат внутри объединения кругов, ограниченных окружностями $\omega_i$ и $\omega_j$.
Действительно, пусть $Z$ - одна из точек пересечения $\omega$ и прямой $l$. Без ограничения общности можно считать, что она лежит на продолжении отрезка $X_kX_i$ за точку $X_i$. Тогда $X_iZ = X_kY - X_kX_i < X_iY$, так что $Z$ лежит внутри окружности $\omega_i$. Лемма доказана.
В силу леммы, если провести окружности с центрами в отмеченных $n + 1$ точках и радиусами, равными названным Мишей для этих точек расстояниям, то одна из точек пересечения окружностей, соответствующих соседним точкам, будет загаданной. Причем из двух точек пересечения окружностей следует взять ту, которая лежит с той же стороны, что и круг, данный в условии задачи. Поэтому если Коля последовательно назовет все такие точки пересечения окружностей ($n$ попыток), то хотя бы один раз названное Мишей расстояние будет нулевым.
Итак, мы за $2n + 1$ попытку угадали одну точку. Действуя далее аналогично, мы отгадаем все точки за
$(2n + 1) + (2n - 1) + \cdots + 3 = (n + 1)^2 - 1$
попыток.
Ответ: Может.
На прямоугольном листе бумаги нарисован круг, внутри которого Миша мысленно выбирает $n$ точек, а Коля пытается их разгадать. За одну попытку Коля указывает на листе (внутри или вне круга) одну точку, а Миша сообщает Коле расстояние от нее до ближайшей неразгаданной точки. Если оно оказывается нулевым, то после этого указанная точка считается разгаданной. Коля умеет отмечать на листе точки, откладывать расстояния и производить построения циркулем и линейкой. Может ли Коля наверняка разгадать все выбранные точки менее, чем за $(n + 1)^2$ попыток?
Решение:
Покажем сначала, как за $2n+1$ попытку отгадать одну точку. Пусть прямая $l$ не пересекает круг из условия задачи, проведем отрезок этой прямой и отметим на нем $n+1$ точку $X_0, \cdots , X_n$. Узнаем для каждой из них расстояние до ближайшей загаданной точки. По принципу Дирихле , хотя бы для двух (скажем, $X_i$ и $X_{j,i} < j$) из отмеченных $n + 1$ точек Миша назовет расстояние до одной и той же неизвестной нам загаданной точки $Y$.
Лемма. Для всех k таких, что $i < k < j$, Миша также назовет расстояние до точки $Y$.
Доказательство. Пусть $\omega_i$ и $\omega_j$ - окружности с центрами в точках $X_i$ и $X_j$ соответственно, проходящие через точку $Y$. Пусть $Y^{ \prime}$ - вторая точка пересечения этих окружностей (случай касающихся окружностей мы оставляем читателю). Пусть $\omega$ - окружность с центром в точке $X_k$, проходящая через точки $Y$ и $Y^{ \prime}$ (рис.). Достаточно доказать, что окружность $\omega$ содержится внутри объединения кругов, ограниченных окружностями $\omega_i$ и $\omega_j$.
Заметим сначала, что $\omega$ пересекает $\omega_i$ и $\omega_j$ только в точках $Y$ и $Y^{ \prime}$ (так как окружности пересекаются не более чем в двух точках). Значит, каждая из дуг, на которые окружность разбивается точками $Y$ и $Y^{ \prime}$, либо лежит целиком внутри объединения кругов, либо целиком снаружи. Чтобы доказать, что второй случай невозможен, достаточно проверить, что точки пересечения $\omega$ и прямой $l$ лежат внутри объединения кругов, ограниченных окружностями $\omega_i$ и $\omega_j$.
Действительно, пусть $Z$ - одна из точек пересечения $\omega$ и прямой $l$. Без ограничения общности можно считать, что она лежит на продолжении отрезка $X_kX_i$ за точку $X_i$. Тогда $X_iZ = X_kY - X_kX_i < X_iY$, так что $Z$ лежит внутри окружности $\omega_i$. Лемма доказана.
В силу леммы, если провести окружности с центрами в отмеченных $n + 1$ точках и радиусами, равными названным Мишей для этих точек расстояниям, то одна из точек пересечения окружностей, соответствующих соседним точкам, будет загаданной. Причем из двух точек пересечения окружностей следует взять ту, которая лежит с той же стороны, что и круг, данный в условии задачи. Поэтому если Коля последовательно назовет все такие точки пересечения окружностей ($n$ попыток), то хотя бы один раз названное Мишей расстояние будет нулевым.
Итак, мы за $2n + 1$ попытку угадали одну точку. Действуя далее аналогично, мы отгадаем все точки за
$(2n + 1) + (2n - 1) + \cdots + 3 = (n + 1)^2 - 1$
попыток.
Ответ: Может.
