Считалочка с негром

Старый вариант загадки-считалочки, где надо найти начальную точку для счёта:

На судне находится 20 человек, между ними один негр. Вследствие недостатка в продовольствии один из команды должен быть выброшен за борт. Решено отсчитывать по семи и каждого седьмого освобождать; дойдя до конца ряда, переходить к его началу, не прерывая счёта. Оставшийся последним должен умереть. Негр (обозначенный перевернутой спичкой) может стать на любое место в ряду. С кого следует начинать счёт, чтобы негр оставался всегда последним?

Ответ:

Эта задача является вариантом задачи Иосифа Флавия.

Есть несколько способов её решения, а один из способов - с использованием рекуррентных соотношений.

Обозначим исходное число человек - n. Число человек, которое отсчитываем каждый раз - m, k - позиция последнего оставшегося человека (в нашем случае это негръ).

Тогда k можно выразить через рекуррентное соотношение:

k(n, m) = 1 + (k(n-1, m) + m - 1) mod n,
причём k(1, m) = 1.

Ниже приведена интерактивная иллюстрация этого решения. Как видите, чтобы при условиях, изображённых на иллюстрации к загадке, негръ оказался последним, надо начинать счёт с человека номер 6.

Кликните по клетке, чтобы выбрать начало счёта: