Информация о задаче

Задача 105192

Темы:	[	Двоичная система счисления	]
	[	Разбиения на пары и группы; биекции	]
	[	Объединение, пересечение и разность множеств	]
	[	Целая и дробная части. Принцип Архимеда	]
	[	Экстремальные свойства (прочее)	]

Сложность: 7
Классы: 10,11

Прислать комментарий

Условие

Автор: Косухин О.Н.

Вдоль стены круглой башни по часовой стрелке ходят два стражника, причём первый из них — вдвое быстрее второго. В этой стене, имеющей длину 1, проделаны бойницы. Система бойниц называется надёжной, если в каждый момент времени хотя бы один из стражников находится возле бойницы.

а) Какую наименьшую длину может иметь бойница, если система, состоящая только из этой бойницы, надежна?

б) Докажите, что суммарная длина бойниц любой надёжной системы больше 1/2.

в) Докажите, что для любого числа s>1/2 существует надёжная система бойниц с суммарной длиной, меньшей s.

Решение

а) Предположим, что бойница имеет длину 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], обладающее следующими свойствами:

A есть объединение конечного числа непересекающихся отрезков;
суммарная длина этих отрезков не превосходит s;
если 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):

t = 0, a₁a₂a₃...

(все 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), для которых ни один из наборов вида

a_{kn + 1}a_{kn + 2}...a_{(k + 1)n} (k = 0, 1,..., q - 1)

не совпадает с набором 1 $\underbrace{00 \dots 0}_{n-1}^{} \,$ ) Суммарная длина полуинтервалов, составляющих множество G_q, равна)

g_q = $\displaystyle \Bigl($ $\displaystyle { \frac{2^n-1}{2^n}}$ $\displaystyle \Bigr)^{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}^{} \,$ , то число ${ \frac{t'+1}{2}}$ = 0, 1a₁a₂a₃... также содержится в C_q. Ясно, что ${ \frac{t}{2}}$ $\ne$ ${ \frac{t'+1}{2}}$ $\Bigl($ так как ${ \frac{t}{2}}$ < ${ \frac{1}{2}}$ и ${ \frac{t'+1}{2}}$ $\ge$ ${ \frac{1}{2}}$ $\Bigr)$ . Отсюда получаем, что

c_q $\displaystyle \ge$ $\displaystyle { \frac{b_q}{2}}$ + $\displaystyle { \textstyle \frac{1}{2}}$ $\displaystyle \Bigl($ b_q - $\displaystyle { \frac{1}{2^{n-1}}}$ $\displaystyle \Bigr)$ = b_q - $\displaystyle { \frac{1}{2^n}}$ .

Значит, 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, не превосходит

b_q + g_q < $\displaystyle { \textstyle \frac{1}{2}}$ + $\displaystyle { \frac{1}{2^{n+1}}}$ + $\displaystyle { \frac{1}{2^{n+1}}}$ < s,

и свойство 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} является эргодическим.

Источники и прецеденты использования


олимпиада
Название	Московская математическая олимпиада
год
Номер	67
Год	2004
вариант
Класс	11
задача
Номер	6