1.3 ЗАДАЧА ИОСИФА ФЛАВИЯ

Последний из наших предварительных примеров представляет собой один из вариантов античной задачи, носящей имя Иосифа Флавия — известного историка первого века. Существует легенда, что Иосиф выжил и стал известным благодаря математической одаренности. В ходе иудейской войны он в составе отряда из 41 иудейского воина был загнан римлянами в пещеру. Предпочитая самоубийство плену, воины решили выстроиться в круг и последовательно убивать каждого третьего из живых до тех пор, пока не останется ни одного человека. Однако Иосиф, наряду с одним из своих единомышленников, счел подобный конец бессмысленным — он быстро вычислил спасительные места в порочном круге, на которые поставил себя и своего товарища.

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

только один человек. Вот, к примеру, исходное расположение при

Порядок исключения так что остается номер 5. Задача: определить номер уцелевшего,

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

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

Итак, допустим, что первоначально имеется людей. После первого прохода по кругу мы остаемся с номерами

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

Теперь можно быстро продвигаться к большим Например, нам известно, что поэтому

Аналогично, и вообще можно вывести, что

Ну, а как насчет нечетного случая? Оказывается, что в случае людей жертва с номером 1 уничтожается сразу после жертвы с номером и мы остаемся с номерами

Опять получили почти первоначальную ситуацию с людьми, но на этот раз номера уцелевших удваиваются и увеличиваются на 1. Таким образом,

Объединение этих уравнений с дает рекуррентное соотношение, которое определяет во всех случаях:

Вместо получения из это рекуррентное соотношение действует значительно более „эффективно" поскольку оно каждый раз уменьшает величину вдвое и более. Скажем, можно вычислить применяя только 19 раз. Но мы по-прежнему хотим найти выражение для в замкнутой форме, поскольку оно будет более информативным и позволит вычислять решение еще быстрее. В конце концов, это ведь вопрос жизни или смерти.

Наше рекуррентное соотношение дает возможность очень быстро составить таблицу первых значений Быть может, оно поможет нам так же быстро заметить закономерность и угадать ответ:

Вот . Оказывается, если сгруппировать значения по степеням 2 (в таблице эти группы отделены вертикальными линиями), то в каждой группе всегда будет начинаться с 1, а затем увеличиваться на Итак, если записать в виде где — наибольшая степень 2, не превосходящая , что остается, то решение нашего рекуррентного соотношения, по-видимому, должно быть таким:

(Заметим, что если то остаток удовлетворяет неравенству

Теперь надо доказать (1.9). Как и прежде, мы будем использовать индукцию, но на этот раз — индукцию по . При имеем таким образом, база для (1.9) сводится к равенству которое не вызывает сомнений. Индуктивный шаг состоит из двух частей в зависимости от того, четно или нечетно I. Если то I четно и

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

В любом случае индукция выполнена и справедливость (1.9) установлена.

С целью иллюстрации решения (1.9), вычислим . В этом случае так что

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

Степени 2 играли важную роль в нашем поиске решения, так что естественно обратиться к двоичным представлениям величин Допустим, что двоичные разложения величин имеют вид

т. е.

где каждое равно 0 или 1, причем старший бит равен 1. Вспоминая, что последовательно получаем:

(Последнее следует из того, что Мы доказали, что

т. е., на программистском жаргоне, получается путем циклического сдвига двоичного представления влево на один бит! Мистика. Например, если то что равно Если бы мы имели дело с двоичной записью с самого начала, то, вероятно, сразу же бы наткнулись на эту закономерность.

Если мы начинаем итерируем -функцию раз, то тем самым осуществляем циклический сдвиг на битов; а поскольку является -битовым числом, мы могли бы рассчитывать в итоге снова получить Но это не совсем так. К примеру, если то но затем и процесс обрывается: когда 0 становится старшим битом — он пропадает. В действительности всегда должно быть по определению, ибо есть номер уцелевшего; следовательно, если мы никогда не сможем получить снова в последующих итерациях.

Многократное применение порождает последовательность убывающих значений, достигающих в конце концов „неподвижной точки“ , такой, что Свойство циклического сдвига позволяет легко выяснить, что это будет за точка: итерирование функции и более раз всегда будет порождать набор из одних единиц со значением — 1, где -число равных 1 битов в двоичном представлении . Так, поскольку имеем

аналогично,

Странно, но факт.

Давайте ненадолго вернемся к нашему первоначальному предположению, что при четном Вообще-то это неверно, но теперь мы как раз в состоянии выяснить, когда это верно:

Если число целое, то будет решением, поскольку I меньше, чем . Нетрудно убедиться, что кратно 3, когда нечетно, но не когда четно. (Мы будем изучать подобные вещи в гл. 4.) Поэтому имеется бесконечно много

решений уравнения и первые — такие:

Обратите внимание на крайний правый столбец. Это двоичные числа, циклический сдвиг которых на одну позицию влево дает тот же самый результат, что и обычный сдвиг на одну позицию вправо (деление пополам).

Отлично, мы достаточно основательно разобрались с функцией следующий этап — ее обобщение. Что бы случилось, если бы в нашей задаче возникла рекуррентность, схожая с (1.8), но с другими константами? Тогда мы вряд ли могли бы рассчитывать угадать решение, поскольку оно было бы воистину таинственным. Исследуем этот случай, введя константы , и попытаемся найти решение в замкнутой форме для более общего рекуррентного соотношения

(В нашем первоначальном рекуррентном соотношении было Начиная с оси прибегая к ранее опробованному способу, можно составить следующую сводную таблицу для малых значений

Похоже, что коэффициенты при равны наибольшим степеням 2, не превосходящим Кроме того, между последовательными степенями 2 коэффициенты при уменьшаются на 1 вплоть до 0, а при у увеличиваются на 1, начиная с 0. Поэтому, если выразить в виде

разделяя зависимость от и у, то, по-видимому,

Здесь, как обычно, при

Нельзя сказать, что так уж трудно доказать (1.13) и (1.14) по индукции, но подобные действия бестолковы и малоценны. К счастью, существует лучший способ действия, если выбрать отдельные значения и затем скомбинировать их. Продемонстрируем этот способ на примере частного случая когда функция предполагается равной Тогда (1.11) сводится к рекуррентному соотношению

Достаточно ясно (доказывается индукцией по что

Затем воспользуемся рекуррентным соотношением (1.11) и решением (1.13) в обратном порядке, начав с простой функции и выяснив, нет ли каких-нибудь определяющих ее констант . Подстановка постоянной функции в (1.11) показывает, что

следовательно, значения удовлетворяющие этим уравнениям, дадут Подобным же образом можно подставить

Эти уравнения справедливы при всех когда так что нет нужды доказывать по индукции, что при этих параметрах . Нам уже известно, что в таком случае будет решением, поскольку рекуррентное соотношение (1.11) однозначно определяет при каждом

И теперь, в сущности, блюдо готово! Мы показали, что функции из (1.13), которые определяют решение (1.11) в общем случае, удовлетворяют уравнениям

Наши предположения, сделанные в (1.14), подтверждаются немедленно, поскольку мы можем решить эти уравнения, получая .

Изложенный подход иллюстрирует исключительно полезный репертуарный метод решения рекуррентных уравнений. Сначала мы подбираем величины общих параметров, для которых мы знаем решение, — это обеспечивает нас репертуаром разрешимых частных решений. Затем, комбинируя частные решения, мы получаем общее решение. При этом необходимо столько независимых частных решений, сколько имеется независимых параметров (в нашем случае их было три — для Другие примеры репертуарного подхода содержатся в упр. 16 и 20.

Мы знаем, что первоначальная -рекуррентность имеет мистическое решение в двоичной записи:

А допускает ли обобщенная -рекуррентность подобную мистику?

Конечно, почему же нет? Обобщенную рекуррентность (1.11) можно переписать как

если положить эта рекуррентность развертывается, бит за битом:

Предположим, что теперь мы расширили систему счисления с основанием 2, так что в ней допустимы произвольные цифры, а не только 0 и 1. Предыдущий вывод означает, что

Чудесно. Мы смогли бы заметить это обстоятельство гораздо раньше, если бы составили табл. (1.12) в ином виде:

Например, при значения для исходной -рекуррентности дают

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

Итак, изменение системы счисления привело нас к компактному решению (1.16) обобщенной рекуррентности (1.15). Если нам, право, неймется — можно обобщить ее еще больше. Рекуррентность

совпадает с предыдущей за одним исключением: мы начинаем с чисел по основанию а получаем значения по основанию с. То есть эта рекуррентность имеет решение с переменным основанием

Предположим, к примеру, что вследствие некоторого благоприятного стечения обстоятельств нами получено рекуррентное соотношение

и, допустим, мы хотим вычислить . Здесь . Тогда и решение по переменному основанию позволяет осуществить переход от основания 3 к основанию 10 цифра за цифрой. Так, старшая цифра 2 становится цифрой 5, а 0 и 1 становятся цифрами образуя наш ответ:

Итак, Иосиф и иудейская война привели нас к довольно интересным обобщенным возвратным соотношениям.