|
||||||||||||||||||
|
Эта задача в еще большей степени чем задача 45 навеяна известной
задачей Иосифа Флавия (Josephus problem). Конкурсная задача №75 (А-3) (8 баллов)
Для каждого натурального q, большего 1, опрелелим функцию натурального
аргумента Jq(n) следующим образом:
1. Для каждого q описать все n, для которых Jq(n) = n. Решение
Приведу решение Анатолия Казмерчука.
Из формулы видно, что, если , и n>m, то .
Поэтому, для r = 1,…, q-1 имеем:
Выведем теперь общую формулу для при q > 1.
Представим число n в виде n = s(q-1)+rqk,
где r = 1,…q-1, k = 0,1,2,.., s = 0,…, rqk-1.
Число r даёт тот же остаток при делении на q-1, что и n.
Перейдём теперь к поставленным в задаче вопросам. Обсуждение В классическом варианте задачи Иосифа Флавия наоборот вычеркивается (а не оставляется) каждое q-е число из n, расставленных по кругу. В этом случае явную формулу удается найти лишь для q = 2. Для бОльших q известен лишь достаточно быстрый алгоритм, позволяющий находить номер последнего невычеркнутого числа за время O(q*log(n)), да и то в случае, когда q значительно меньше n. Подробности можно найти, в статье известного марафонца: М.А. Алексеев <Задача Иосифа Флавия>. Империя Математики, 2 (2001), стр. 22-28.
Задача неожиданно для меня удостоилась наивысшей оценки от участников Марафона.
Мне очень приятна такая оценка, но… Награды За верное решение задачи и обобщение второго пункта на любое q Анатолий Казмерчук и Олег Полубасов получают по 9 призовых баллов. За правильное решение здачи Константин Кноп и Виктор Филимоненков получают по 8 призовых баллов. Влад Франк, решивший только первый пункт, получает 3 призовых балла. Эстетическая оценка - 5 баллов
|
|||||||||||||||||
|
||||||||||||||||||
|