Олимпиадная задача по планиметрии: оптимальная длина бойницы в задаче о двух стражниках (Косухин О. Н.)

а) Предположим, что бойница имеет длинуs< 2/3. За то время, пока второй стражник проходит не занятый бойницей участок стены (длины 1 -s), первый стражник пройдет расстояние 2(1 -s) >s. Поэтому найдется такой момент времени, в который ни один из стражников не находится возле бойницы -- противоречие. Значит,s$\ge$2/3. Рассмотрим такой момент времени, в который первый стражник находится на 1/3 впереди второго. Пусть бойница занимает тот участок стены между стражниками, который имеет длину 2/3. Легко проверить, что тогда условия задачи выполнены.

б) Пусть суммарная длина бойниц равна s. Без ограничения общности будем считать, что в начальный момент времени стражники находятся в одной точке, а за 1 час второй стражник делает ровно один обход вдоль стены. Чтобы система бойниц была надежной, необходимо, чтобы суммарное время, проведенное стражниками около бойниц в течении часа, было не меньше часа. Более того, это время должно быть больше часа, так как найдется такой промежуток времени, в течение которого они оба будут находиться возле одной и той же бойницы, содержащей точку их встречи.

С другой стороны, за час каждый стражник проведет возле бойниц s часов (первый стражник пройдет все бойницы дважды, но в два раза быстрее). Итак, 2s > 1, и следовательно s > 1/2.

в) Построим множество A $\subset$ [0;1], обладающее следующими свойствами:

1. A есть объединение конечного числа непересекающихся отрезков;
2. суммарная длина этих отрезков не превосходит s;
3. если t $\not \in$A, то {2t} $\in$ A (фигурные скобки обозначают дробную часть).

Если такое множество построено, то задачу решить несложно. Как и раньше, считаем, что в момент времени t = 0 стражники находились в одной точке, а за отрезок времени [0;1] второй стражник делает ровно один обход вдоль стены. Поставим в соответствие числу t $\in$ [0;1] точку стены, в которой находится второй стражник в момент t. Пусть бойницы проделаны на участках стены, соответствующих отрезкам, составляющим множество A. Тогда их суммарная длина будет меньше s. Так как для любого t имеем t $\in$ A или {2t} $\in$ A, получаем, что в каждый момент времени по крайней мере один из стражников находится возле бойницы.

Идея построения множества A: допустим, что нам удалось разбить отрезок [0;1] на такие множества A и B, что если t $\in$ A, то

{2t} $\in$ B, а если t $\in$ B, то {2t} $\in$ A. Тогда последнее требование выполняется автоматически. Представим себе на секунду, что множества A и B состоят из отрезков (это, конечно, невозможно). Тогда нетрудно убедиться, что суммарная длина отрезков, составляющих множество A, равна суммарной длине отрезков, составляющих множество B, а значит, равна 1/2. К сожалению, таких множеств A и B не существует (см. комментарий). Тем не менее, можно построить множества A и B, для которых эти условия выполнены "с точностью до s - ${ \frac{1}{2}}$". Этим мы и займемся.

Выберем натуральное число n таким, чтобы ${ \frac{1}{2^n}}$ < s - ${ \frac{1}{2}}$. Можно считать, что n нечетно. Рассмотрим двоичную запись числа t из полуинтервала [0;1):

(всеa_kравны 0 или 1. Пусть задано некоторое натуральное число q. Рассмотрим множество M_qчисел tиз полуинтервала [0;1), для которых среди первыхqn знаков после запятой в двоичном разложении tвстречается набор1$\underbrace{00 \dots 0}^{} \,$. Ясно, чтоM_q представляет собой объединение конечного числа полуинтервалов. Дополнение [0;1) $\setminus$ M_q содержится в множестве G_q тех чисел t из полуинтервала [0;1), для которых ни один из наборов вида не совпадает с набором1$\underbrace{00 \dots 0}_{n-1}^{} \,$) Суммарная длина полуинтервалов, составляющих множество G_q, равна)Поскольку${ \frac{2^n-1}{2^n}}$< 1, тоg_qстремится к нулю при неограниченном росте q(n фиксировано. Поэтому можно взятьqнастолько большим, чтоg_q<${ \frac{1}{2^{n+1}}}$. Можно считать, чтоqчетно. Множество M_q разобьем на два множества B_q и C_q, где B_q -- множество таких чисел t, что набор 1$\underbrace{00 \dots 0}^{} \,$ впервые встречается в двоичной записи числа t, начиная с нечетного места (т. е. наименьшее k$\ge$ 0, для которого набор a_ka_{k + 1}...a_{k + n - 1} совпадает с набором 1$\underbrace{00 \dots 0}^{} \,$, нечетно). Аналогично, C_q -- множество таких чисел t, что набор 1$\underbrace{00 \dots 0}^{} \,$ впервые встречается, начиная с четного места. Обозначим суммарную длину полуинтервалов, составляющих множество B_q, через b_q, а суммарную длину полуинтервалов, составляющих множество C_q, -- через c_q.

Пусть число t = 0, a₁a₂a₃... содержится в B_q, тогда число ${ \frac{t}{2}}$ = 0, 0a₁a₂a₃... содержится в C_q (здесь мы используем то, что n нечетно, а q четно). Кроме того, если набор

a₁a₂...a_{n - 1} первых цифр числа t' не совпадает с набором

$\underbrace{00 \dots 0}^{} ,$, то число

= 0, 1a₁a₂a₃... также содержится в C_q. Ясно, что ${ \frac{t}{2}}$$\ne$ $\Bigl($так как ${ \frac{t}{2}}$ < ${ \frac{1}{2}}$ и $\ge$${ \frac{1}{2}}$$\Bigr)$. Отсюда получаем, что

Значит,b_q< 1 -c_q$\le$1 +${ \frac{1}{2^n}}$-b_q, т. е.b_q<${ \frac{1}{2}}$+${ \frac{1}{2^{n+1}}}$. Положим A' = B_q $\cup$ G_q. Тогда A' -- объединение попарно непересекающихся полуинтервалов. Искомое множество A получается из множества A' заменой всех полуинтервалов на отрезки.

Свойство 1 очевидно. Суммарная длина отрезков, составляющих множество A, не превосходит

и свойство 2 доказано. Для доказательства последнего свойства заметим, что еслиt$\not \in$A, тоt= 0,a₁a₂... содержится в множестве C_q, т. е. среди первыхqnзнаков после запятой встречается набор1$\underbrace{00 \dots 0}^{} \,$, причем он впервые встречается, начиная с четного места. Тогда{2t} = 0,a₂a₃..., так что {2t} принадлежит множеству B_q$\subset$A. Комментарий. Обозначим $\phi$(x) = {2x}. Тогда $\phi$ можно рассматривать как отображение единичной окружности в себя. Можно было бы пытаться решить задачу следующим образом: разобьем окружность на множества A и B так, что $\phi$(A) = B и $\phi$(B) = A. "Приблизим" множество A объединением отрезков и возьмем это множество отрезков в качестве бойниц. Нетрудно видеть, что если множества A и B измеримы, то мера каждого из них равна 1/2. Однако оказывается, что такие множества A и B не могут быть измеримыми! Это связано с тем, что отображение $\phi$($\phi$(x)) = {4x} является эргодическим.

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