Сорок один человек стоит в кольце, и каждый второй выбывает, круг за кругом, пока не останется один. Где вам стоять? Ответу нужно одно вычитание: возьмите наибольшую степень двойки, не превосходящую 41, то есть 32, удвойте остаток и прибавьте единицу. 41 − 32 = 9, и 2 × 9 + 1 = 19. Первая ссылка делает всё это в одну строку, вторая показывает 2⁵ = 32, а третья — остаток 9, которым формула питается. Степени двойки появляются потому, что один круг счёта ровно вдвое уменьшает кольцо, и выживший — это каждый раз нечётный человек, когда кольцо подрезано до размера, который узор выдерживает.
История Иосифа Флавия — не эта игра. Он и сорок соратников, как считается, были заперты в пещере в 67 году н. э. и договорились убивать друг друга по счёту вместо того, чтобы сдаться; Иосиф, по преданию, устроил счёт так, что остался сам. Если выбывает не каждый второй, а каждый третий, то последний из 41 — номер 31, число, которое называют источники. Вариант k = 2 — тот, что укладывается в формулу в одну строку, и в учебниках он всплывает именно потому, что 41 достаточно мало, чтобы проверить вручную, и достаточно велико, чтобы ответ не был очевиден: 19 трудно угадать и легко проверить.
Ответ
19
Как его читать
2·(41 − 2⁵) + 1 в поле вычислений. Вторая ссылка — степень двойки, которую формула вычитает, третья — остаток, который она удваивает.
Источник
Flavius Josephus, The Jewish War III, on the siege of Jotapata in 67 CE; the counting-out game named after him has the closed form J(n) = 2(n − 2^⌊log₂ n⌋) + 1 when every second person leaves the circle
Пересчитать в калькуляторе
Эти ссылки открывают подходящий калькулятор с уже введёнными числами этой задачи. Строка выше — то, что должен показать экран; проверьте сами.