Question

239 шпионов сидят по одному в 239 конспиративных квартирах. Каждый шпионит за ближайшей к нему конспиративной квартирой (расстояния между квартирами различны). Докажите, что есть шпион, который может пойти на задание, поскольку за ним никто не следит.

Answer 1

Рассмотрим i-го шпиона в i-той квартире. Пусть j-тая квартира ближайшая к нему и он следит за ней. Но, т. к. все расстояния между квартирами различны, то для j-го шпиона в j-той квартире ближайшей будет i-тая квартира. Следовательно он будет следить за i-тым шпионом. Точно так же, если шпион из k-той квартиры следит за шпионом из ближайшей к нему m-той квартиры, то шпион из m-той квартиры будет следить за шпионом из k-той квартиры. Следвательно всех шпионов можно разбить на пары, следящие друг за другом, но т. к. 239 = 119*2 + 1, то один шпион остается без пары и может пойти на задание, т. к. за ним никто не следит.

Answer 2

Для доказательства этого утверждения используем метод противоположного доказательства.

Предположим, что каждый шпион наблюдает за своей ближайшей конспиративной квартирой, то есть нет шпиона, за которым никто не следит. Докажем, что это предположение неверно.

Изначально, у каждого шпиона есть ровно одна конспиративная квартира, за которой он наблюдает. Разместим эти квартиры на числовой прямой, где каждая квартира будет иметь своё расположение по оси. Поскольку всего 239 шпионов и 239 квартир, каждый шпион наблюдает за своей квартирой.

Теперь рассмотрим первого шпиона, который наблюдает за квартирой с наименьшим расстоянием до него. Пусть это расстояние равно d1. Так как за каждым шпионом наблюдает хотя бы один другой шпион (они все размещены в разных квартирах), то расстояние между этими шпионами не может быть меньше d1 - иначе бы другой шпион наблюдал бы за квартирой первого шпиона. То есть, между первым и вторым шпионом расстояние хотя бы d1.

Аналогично, для первого шпиона расстояния до шпионов, следующих после него, будут не меньше d1.

Рассмотрим последнего шпиона, который наблюдает за квартирой с наибольшим расстоянием до него. Пусть это расстояние равно d2. Поскольку за каждым шпионом наблюдает хотя бы один другой шпион, то расстояние между этими шпионами не может быть меньше d2 - иначе бы другой шпион наблюдал бы за квартирой последнего шпиона. То есть, между предпоследним и последним шпионом расстояние хотя бы d2.

Аналогично, для последнего шпиона расстояния до шпионов, стоящих перед ним, будут не меньше d2.

Таким образом, из построенного ранее ряда шпионов, каждый следующий шпион находится на расстоянии не меньше d1 от предыдущего и на расстоянии не меньше d2 от последнего шпиона.

Поскольку всего 239 шпионов, мы можем утверждать, что d1 + d2 ≤ 239, так как в противном случае мы бы получили больше 239 квартир.

Теперь мы можем рассмотреть шпиона, которому соответствует максимальное из чисел d1 и d2 (пусть это будет d). По построению, он будет следить за квартирой, которая находится на расстоянии от его квартиры не меньше, чем d.

Однако, за ним никто не следит, поскольку весь пространственный интервал между его квартирой и следующим шпионом занят другими квартирами, за которыми кто-то следит. Таким образом, утверждение о том, что за каждым шпионом наблюдает хотя бы один другой шпион, оказывается недоказуемым при наших предположениях.

Значит, предположение о том, что каждый шпион следит за своей квартирой, неверно. Таким образом, существует шпион, за которым никто не следит, и он может пойти на задание.