Логические загадки - Учитесь решать правильные задачи.

Логические загадки: Учитесь решать правильные задачи.
Эта задача является вариантом задачи Иосифа Флавия.

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

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

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

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

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

  • 3661
  • Помощь
  • Интересно
    +3
    Нет

1 ответ

avatar
Учтем то, что негр может занять любую позицию. Итак, если считаем слева на право, то счет начинаем за одного человека до негра (в данном случае 6 спичка справа), если с правой стороны (с 11 спички). В этом случае при сквозном счете, негр всегда будет последним
  • 0