Считалка на выживание

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

В давние времена, когда Римская империя еще вела победоносные войны на Африканском континенте, еврейский отряд со своим предводителем Иосифом Флавием оказался окружен в пещере. Бойцы заявили, что предпочитают принять смерть от рук товарищей, лишь бы не сдаваться в плен римлянам. Они ожидали того же от своего предводителя. Иосиф не мог противостоять целому отряду и пошел на хитрость: предложил выстроить отряд в круг и убивать каждого второго до тех пор, пока не останется только один человек. С какого бойца нужно начать отсчет Иосифу, чтобы остаться последним выжившим, если под его предводительством воевало сорок человек? Итак, начинается «считалка на выживание»!

Вопрос можно сформулировать по-другому: на место с каким номером следует встать Иосифу? В оригинальной задаче в круге оказалось n = 41 человек, но для начала можно рассмотреть значительно меньшее количество. Например, при n = 6 последовательно выбывают номера 2, 4, 6, 3, 1 – выжившим оказывается человек на месте номер 5, для n = 7 искомый номер – 7, а для n = 8 – 1.

На последний пример следует обратить особое внимание. Здесь число людей в кругу является степенью числа 2, и уменьшается ровно вдвое после каждого круга: обязательно выбывает человек с максимальным номером на данный момент, и отсчет продолжается с первой позиции – она никогда не бывает второй. Это правило легко обобщается на остальные степени 2: для n = 2^k Иосифу следует начинать отсчет с самого себя.

Но как быть во всех остальных случаях? Допустим, что k – такое число, что n лежит между 2^k и 2^(k+1). Тогда n можно представить в виде 2^k + L, где L < 2^k и 2L < n. Почему же именно такое разбиение окажется удобным? Существует способ свести задачу с произвольным числом людей n к задаче, для которой число людей будет степенью 2. Давайте посмотрим, как будет выглядеть круг после L шагов. Возьмем n = 7, тогда k будет равно двум, а L – трем:

В круге осталось 2^k человек, при этом первым номером для нового круга будет номер, следующий за последним выбывшим – тем, который был удален на шаге L. Именно на этом месте должен стоять Иосиф – как мы уже определили для случая задачи с n = 2^k. Так как выбывает каждый второй и ровно один человек на каждом шаге, искомый номер равен 2L + 1 – заметим, что 2L строго меньше n, поэтому такой номер всегда существует.

Подведем итоги. Чтобы выжить, Иосифу нужно вычесть из n = 41 максимально возможную степень 2 – в данном случае k = 5, получить число L = 41 – 2^5 = 9 и вычислить место, на которое нужно встать: 2L + 1 = 19. Таким образом, мы с вами получили решение задачи в общем виде, а Иосиф – длинную и, будем надеяться, счастливую жизнь.