Бесконечность в задачах

32

Бесконечность в задачах

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

Фигуры на плоскости

1. Можно ли покрыть плоскость бесконечным числом квадратов, среди которых ровно два одинаковых? Квадраты не могут перекрываться.

Ответ: да, можно. Нарисуем квадрат со стороной 1, приставим к нему слева квадрат со стороной 1, чтобы получился прямоугольник 1 ѣ 2, к этому прямоугольнику приставим снизу квадрат со стороной 2, чтобы получился прямоугольник 2 ѣ 3, к нему приставим справа квадрат со стороной 3 и так далее: будем заполнять плоскость «по спирали», каждый раз приставляя к имеющейся фигуре квадрат так, чтобы его сторона совпала с одной из сторон фигуры. Ясно, что любая точка плоскости будет покрыта одним из квадратов. Кстати, длины сторон этих квадратов образуют последовательность Фибоначчи 1, 1, 2, 3, 5, 8, 13, …– подробно о ней рассказано в этом номере журнала в рубрике «Математический кружок». Подумайте над более сложным вопросом: можно ли покрыть плоскость бесконечным числом неперекрывающихся квадратов, среди которых нет одинаковых?

2. Можно ли покрыть плоскость конечным числом а) внутренностей парабол; б) внутренностей углов, сумма которых меньше 360 o?

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

Бесконечные графы 3. Пусть известно, что человечество бессмертно, а каждый человек смертен. Число людей в каждом поколении конечно. Докажите, что найдется бесконечная цепочка мужчин, начинающаяся с Адама (каждый следующий в цепочке – сын предыдущего).

Построим такую картинку. На первом этаже разместим одну точку – она будет изображать Адама. Из нее выпустим

столько стрелок, сколько было у Адама сыновей, на второй этаж (концы стрелок соответствуют сыновьям Адама). Из каждой точки–человека второго этажа выпустим стрелки на третий этаж (стрелки опять соответствуют сыновьям), и так далее. Получим систему точек и стрелок из бесконечного числа этажей (так как человечество бессмертно), но на каждом этаже будет конечное число точек. Ясно, что есть бесконечное количество конечных путей, идущих по стрелкам, с началом в точке первого этажа. Надо доказать, что есть бесконечный путь. Объясним, как его найти. Первой в нем будет точка первого этажа. Так как есть бесконечно много путей, ведущих из точки первого этажа, то на втором этаже найдется точка, через которую проходит бесконечно много путей. Эта точка будет второй в нашем пути. Рассмотрим все пути, проходящие через выбранные две точки, – их бесконечно много, и значит, на третьем этаже найдется точка, через которую проходит бесконечно много из них. Выберем ее третьей. Каждый раз мы сможем достраивать наш путь, увеличивая его длину, и в итоге получится бесконечный путь.

4. Имеется язык с конечным алфавитом. Словом в этом языке называется любая (конечная или бесконечная) последовательность букв из алфавита этого языка. Часть слов (конечной длины) в языке – неприличные. Назовем слово абсолютно приличным, если в нем нет неприличных подслов. Известно, что существуют сколь угодно длинные абсолютно приличные слова. Докажите, что существует бесконечно длинное абсолютно приличное слово.

Преследования на плоскости 5. Игра происходит на плоскости. Играют двое: первый передвигает одну фишку-волка, второй – 99 фишек-овец. После хода волка ходит одна из овец, затем после следующего хода волка – опять какаянибудь из овец и т.д. И волк, и овцы передвигаются за один ход в любую сторону не более чем на один метр. Верно ли, что при любой первоначальной позиции волк поймает хотя бы одну овцу (окажется с ней в одной точке)?

Ответ: неверно. Нарисуем на плоскости 100 параллельных прямых так, чтобы расстояние между соседними прямыми равнялось 3 метрам. Разместим овец на разные прямые, каждая в дальнейшем будет двигаться только по своей прямой. Волка поместим на сотую прямую. Приведем алгоритм поведения овец, при котором расстояние от волка до любой овцы перед ходом волка всегда будет больше метра. Если расстояние от волка до каждой из овец больше метра, двигаем любую овцу (вдоль ее прямой) так, чтобы она удалилась от волка. Как только волк приближается к какой-то из овец на расстояние 1 метр или ближе (такая овца может быть ровно одна), сдвигаем овцу по ее прямой в одну из сторон на 1 метр так, чтобы расстояние между ней и волком стало больше метра.

6. Город представляет собой бесконечную клетчатую плоскость (линии – улицы, клеточки – кварталы). На одной из улиц через каждые 100 кварталов на перекрестках стоит по милиционеру. Где-то в городе есть бандит (его местонахождение неизвестно, но перемещается он только по улицам). Цель милиции – увидеть бандита. Есть ли у милиции алгоритм наверняка достигнуть своей цели? Максимальные скорости милиции и бандита – какие-то конечные, но неизвестные нам величины (у бандита скорость может быть больше, чем у милиции). Милиция видит вдоль улиц во все стороны на бесконечное расстояние.

Выберем систему координат так, чтобы милиционеры стояли на улице y = 0 в точках (0; 0), (100; 0), (–100; 0), (200;0), (–200;0) и т.д. Пусть милиционеры, стоящие в точках вида (200k; 0), где $k = 0, \pm 1, \pm 2, K$, останутся на месте. Тогда бандит окажется внутри некоторой полосы между прямыми x = 200m и x = 200(m + 1); он сможет двигаться внутри это полосы, но не сможет выбраться за ее пределы. Остальные милиционеры (назовем их патрульными) пусть движутся по улице y = 0 в направлении точки (0; 0) до ближайшего к ней перекрестка, до которого еще не доходил никто из патрульных. Дойдя до перекрестка (n; 0), патрульный сворачивает на перпендикулярную улицу и движется по ней до точки (n; n) и там останавливается. В результате постепенно патрульные будут занимать все перекрестки на прямой y = x. Докажите, что, действуя таким образом, милиционеры через некоторое время смогут увидеть бандита.

7*. В городе из предыдущей задачи трое полицейских ловят вора (местонахождение вора неизвестно, но перемещается он только по улицам). Максимальные скорости у полицейских и вора одинаковы. Вор считается пойманным, если он оказался на одной улице с полицейским. Как полицейским поймать вора?

Бесконечные десятичные дроби

8. Докажите, что любое действительное положительное число можно представить в виде суммы девяти чисел, десятичная запись каждого из которых состоит только из цифр 0 и 8.

Легко представить любое положительное число в виде суммы девяти чисел, запись которых состоит только из нулей и единиц (проверьте). Теперь решим исходную задачу. Пусть нам надо представить число a. Представим сначала число a/8 в виде суммы девяти чисел, записи которых состоят только из нулей и единиц, а затем домножим каждое из этих чисел на 8 – получим искомые 9 чисел, сумма которых равна a.

9. Докажите, что в любой бесконечной десятичной дроби можно так переставить цифры, что полученная дробь станет периодической (возможно, с предпериодом).

Если в записи дроби есть цифры, встречающиеся в этой записи конечное число раз, то перенесем их все в начало (запишем подряд сразу после запятой). Остальные цифры встречаются бесконечное число раз. Пусть это, например, цифры 2, 5, 7 и 8. Тогда можно переносить их последовательно в начало так, чтобы они шли в порядке 257825782578… В итоге получится периодическая дробь.

Роботы на клетчатой плоскости Робот – это машина с конечной памятью, способная выполнять программу конечной длины. У робота есть несколько флажков. Робот может выполнять следую- щие действия: – попав в клетку, проверить, есть ли там флажок; – сдвинуться на одну из соседних клеток (на плоскости – влево, вправо, вверх, вниз); – установить или снять флажок в клетке, где робот находится. 10. Робот с двумя флажками стоит на одной из клеток бесконечной клетчатой полоски шириной в одну клетку. Как ему действовать, чтобы обойти всю полоску, т.е. побывать на каждой ее клетке хотя бы раз?

Ставим в клетку флажок, сдвигаемся влево, ставим в клетку второй флажок. Далее действуем по очень простому алгоритму: сдвигаемся вправо, пока не дойдем до флажка, снимаем флажок, сдвигаемся еще на клетку вправо, ставим флажок и движемся влево до флажка, передвигаем его на клетку влево и возвращаемся в начало алгоритма (движемся вправо до флажка и т.д.).

11. Как роботу с четырьмя флажками обойти клетчатую плоскость? Можно ли обойтись тремя флажками?

Алгоритм «обходить плоскость по спирали», чередуя ходы влево, вверх, вправо и вниз, периодически увеличивая длину хода на 1 клетку, не годится: роботу придется запоминать все бóльшие и бóльшие числа, а его память конечна. Расположим четыре флажка в клетках квадрата 2 ѣ 2. Далее будем «расширять» квадрат, например так. Сдвигаем левый верхний флажок влево и вверх, идем из этой клетки вправо, проверяя, нет ли под нами флажка. Если есть, сдвигаем его вправо и вверх, затем из этой клетки идем вниз, проверяя, нет ли слева от нас флажка, и так далее. В результате мы будем обходить плоскость, двигаясь «по спирали». Оказывается, достаточно даже трех флажков (подсказка изображена на рисунке).

12. Сможет ли робот обойти клетчатое трехмерное пространство, имея всего три флажка? 13. Как роботу обойти клетчатую полуплоскость, имея всего один флажок? Граница полуплоскости является стенкой. Изначально робот стоит у стенки. Робот видит стенку, когда оказывается рядом с ней. 14. На плоскость высадили двух совершенно одинаковых роботов. У каждого есть несколько флажков. Робот отличает свои флажки от чужих. Как им встретиться? Программы у них должны быть одинаковыми.

Если бы у роботов могли быть разные программы, то организовать встречу было бы легко: один робот стоит на месте, а другой обходит плоскость, используя три флажка. Но роботы сделаны на одном конвейере, и программы поведения у них одинаковые. Попробуйте придумать программу, позволяющую роботам встретиться, используя как можно меньше флажков.

Материал подготовили С.Дориченко, А.Николаев