Представьте, что вам нужно переложить 100 яиц из корзины в коробки поштучно, причем после каждых двух помещений яиц в коробку одно яйцо возвращается обратно в корзину. Хотя этот способ упаковки безусловно неэффективен, понятно, что рано или поздно все яйца будут упакованы. Каждый ход (или шаг) представляет собой помещение одного яйца в коробку или возвращение яйца из коробки в корзину.
Предположим теперь, что в корзине находится произвольное конечное число яиц. Пока оно не задано и может быть сколь угодно большим, задача неограниченна. Но как только начальное количество яиц зафиксировано, существует конечная верхняя грань, ограничивающая число ходов, необходимое для выполнения задания. Если правилами разрешается в любой момент возвращать обратно в корзину любое число яиц, то положение в корне меняется — верхней грани для числа ходов, необходимого для выполнения задания, уже не существует, даже если в корзине сначала было всего лишь два яйца.
В зависимости от правил задача перекладки конечного числа яиц может быть либо конечной, либо бесконечной, либо такой, что сделать ее конечной или бесконечной в вашей воле. Рассмотрим теперь несколько развлекательных математических задач со следующей характерной особенностью. Интуитивно вам кажется, что задачу можно решать сколько угодно долго, в то время как в действительности нет возможности избежать ее завершения за конечное число ходов.
Наш первый пример взят из статьи Р. М. Шмульяна — философа, писателя и логика. Представьте, что у вас неограниченный запас бильярдных шаров, помеченных положительными целыми числами, причем шаров каждого номера — неограниченное количество. Имеется также ящик, в котором находится конечное число пронумерованных шаров. Ваша цель — опустошить ящик. За один шаг можно вынуть шар и заменить его любым конечным числом шаров более низкого ранга. Исключение составляют лишь шары с номером 1: для них замена невозможна, поскольку шаров более низкого ранга нет.
Опустошить ящик за конечное число ходов довольно просто: каждый шар с номером больше 1 заменяем шаром 1, после чего один за другим вынимаем все шары. Правила, однако, позволяют заменить шар с номером больше 1 любым конечным числом шаров более низкого ранга. Например, шар ранга 1000 можно заменить миллиардом шаров ранга 999 плюс 10 миллиардов шаров ранга 998 плюс миллиард миллиардов шаров ранга 997 и т. д.
При таком способе число шаров в ящике с каждым ходом может невообразимо увеличиваться. Не придется ли вам опустошать ящик вечно? Как это ни кажется неправдоподобным, избежать завершения задачи невозможно. Заметим, что неограниченность числа ходов, необходимого для полного опустошения ящика, в этой задаче нам кажется более очевидной, чем в задаче с яйцами. Здесь не только нет ограничена начальное количество шаров, но в каждый момент шар с рангом выше 1 разрешается заменять каким угодно числом шаров.
Цитируя Дж. X. Конвея, можно сказать, что процедура в данном случае «неограниченно неограниченна». На каждой стадии игры, пока в ящике находится шар с рангом, отличным от 1, невозможно предсказать, как много потребуется ходов, чтобы вынуть все шары, кроме шаров ранга 1. (Если все шары имеют ранг 1, ящик, разумеется, опустеет за число ходов, равное количеству шаров первого ранга.) Как бы то ни было независимо от вашей изобретательности в способах замены шаров после конечного числа ходов ящик все-таки опустеет. При этом предполагается, что хотя вы и не бессмертны, но будете жить достаточно долго, чтобы решить задачу.
Этот поразительный результат Шмульян представил в статье «Деревья и игры с шарами» . В ней приводится несколько доказательств, в том числе и простое доказательство по индукции. Я цитирую Шмульяна, потому что ничего лучше предложить не могу: «Если все шары в ящике ранга 1, то понятно, что игра проиграна. Предположим, что наивысший ранг любого шара в ящике равен 2. Тогда в начале имеется конечное число шаров ранга 2 и конечное число шаров ранга 1. Нельзя выбрасывать шары с единицей вечно, следовательно, рано или поздно нам придется выбросить одну из двоек.
Тогда в ящике станет на одну двойку меньше (зато, возможно, намного больше единиц, чем в начале). Но опять невозможно вечно вынимать единицы, рано или поздно мы снова вынем двойку. Понятно, что после конечного числа шагов мы выбросим последнюю двойку и тогда вернемся к ситуации, когда в ящике останутся только единицы. Мы уже знаем, что такая ситуация проигрышная, и, стало быть, доказано, что процесс должен завершиться, если наивысший ранг равен 2. А что, если наивысший ранг равен 3? Мы не можем вечно выбрасывать шары ранга 2 (это только что было доказано!). Следовательно, рано или поздно придется выбросить тройку.