Кровожадная загадка

[sly2m]

100 человек стоят в кругу. У одного в руках нож. Он убивает соседа слева и через труп передает нож стоящему за ним. Тот тоже убивает соседа слева и передает нож дальше по кругу. Процесс повторяется покуда в живых не остается единственный персонаж - Дункан МакКлауд. Какова была первоначальная позиция Дункана в кругу?


Правильный ответ - 73. Т.е. 73й по счету хода ножа останется в живых.

Решать задачу можно многими способами. Например в прямую нарисовать на бумаге 100 кружочков и начать их зачеркивать. Или написать себе в помощники программу, воспользоваться таблицей Excel или еще как. Можно начать считать кругами - в первом кругу погибнут все четные номера, во втором каждый второй оставшийся из нечетных, и т.д.

Но если человек не 100, а 1000? Так же совсем запутаешься. Нужно попытаться найти аналитическое решение. В попытках зачеркивания кружочков на бумаге должен возникать некий паттерн. Зачеркивающий рано или поздно догадается, что если количество человек в кругу равно степени двойки - 2, 4, 8, 16, 32 и так далее, то тот, кто начинает, тот и выигрывает, т.е. остается в живых. Это сразу понятно с двумя человеками, не сложно разобраться с четырьмя, дальше становится понятно аналогично.

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

Ближайшая (вниз) к 100 степень двойки это число 64. Тот, кто держит нож в момент, когда в кругу осталось 64 человека - тот и останется жив. Именно он же окажется с ножом в числе 32 выживших, потом 16ти и так далее. Как узнать каким по счету в изначальной цепи он стоял? Или говоря по другому, как должен поступить хитрый Дункан, чтобы остаться только одним, в какое место цепочки заранее встать?

Если осталось 64 человека из 100, значит погибло 100-64=36. Так как резня идет через одного, значит 36*2=72 человека прошло, и тот, у кого нож сейчас 73й по счету.

В комментах правильно подсказывают, для полностью аналитической формулы, с любым количеством участников, ножей и так далее см. так называемую задачу Иосифа Флавия.