Весьма занимательная задачка от Дональда Кнута

Эта задача известна как Задача Иосифа или Игра в жизнь и смерть.

Для начала рассмотрим случай, когда m=1. В этом случае первый человек будет казнен, а оставшиеся девять снова выстроятся в круг. Теперь снова пронумеруем их от 1 до 9 и продолжим казнь каждого первого человека, пока не останется только один человек. Очевидно, что этот человек будет первоначально стоять под номером 10 в кругу.

Теперь рассмотрим произвольное значение m, которое может быть больше 10. Предположим, что первые три казненных будут иметь номера 10, k и k+1. Тогда после их казни останется 7 человек, которые снова выстроятся в круг.

Мы знаем, что первый казненный был под номером 10, а следующие два казненных были под номерами k и k+1. Это означает, что после первой казни оставшиеся люди снова выстроятся в круг, где первый человек будет иметь номер k+2 (если k=9, то первый человек будет иметь номер 1).

Теперь мы должны казнить каждого m-ого человека, но теперь первый человек имеет номер k+2, а не 1. Это означает, что три человека под номерами 10, k и k+1, которые были казнены на предыдущем шаге, находятся в середине круга. Так как m может быть больше 10, то следующий человек, подлежащий казни, не может быть с номером k-1 или k+2 (если k=9, то не может быть с номером 8 или 1), так как тогда он окажется между первыми тремя казненными.

Это означает, что первый казненный не может иметь номер 10, второй казненный не может иметь номер k, а третий казненный не может иметь номер k+1. Таким образом, мы доказали, что первые три казненных не могут иметь номера 10, k и k+1 в любом порядке при любом значении m, которое может быть больше 10.