Старый вариант загадки-считалочки, где надо найти начальную точку для счёта:
На судне находится 20 человек, между ними один негр. Вследствие недостатка в продовольствии один из команды должен быть выброшен за борт. Решено отсчитывать по семи и каждого седьмого освобождать; дойдя до конца ряда, переходить к его началу, не прерывая счёта. Оставшийся последним должен умереть. Негр (обозначенный перевернутой спичкой) может стать на любое место в ряду. С кого следует начинать счёт, чтобы негр оставался всегда последним?
Ответ:
Эта задача является вариантом задачи Иосифа Флавия.
Есть несколько способов её решения, а один из способов - с использованием рекуррентных соотношений.
Обозначим исходное число человек - n. Число человек, которое отсчитываем каждый раз - m, k - позиция последнего оставшегося человека (в нашем случае это негръ).
Тогда k можно выразить через рекуррентное соотношение:
k(n, m) = 1 + (k(n-1, m) + m - 1) mod n, причём k(1, m) = 1.
Ниже приведена интерактивная иллюстрация этого решения. Как видите, чтобы при условиях, изображённых на иллюстрации к загадке, негръ оказался последним, надо начинать счёт с человека номер 6.
Кликните по клетке, чтобы выбрать начало счёта:
Всего человек .
Выбывает каждый .
При начале счёта с номера , из человек последним останется номер .
