Հովսեփոս Փլավիոսի խնդիր

Հովսեփոս Փլավիոսի խնդիր, պատմական ենթատեքստով մաթեմատիկական խնդիր։

Խնդրի հիմքում լեգենդն է, ըստ որի Հովսեփոս Փլավիոսը 40 հոգով պաշտպանում էր Յոդֆատ քաղաքը։ Չցանկանալով գերի հանձնվել հռոմեական գերակշռող ուժերին պայմանավորվում են, որ յուրաքանչյուր երկու զինվոր սպանելու են երրորդին, մինչև չմահանան բոլորը։ Վերջին երկու զինվորը պետք է սպանեին իրար։ Հովսեփոս Փլավիոսը, նպատակ ունենալով ամրոցը հանձնել հռոմեացիներին, արագ հաշվելով ընտրում է զիվորների շարքում այն տեղը, որի դեպքում լինելու էր վերջին երկու զինվորներից մեկը։

Խնդրի ժամանակակից ձևակերպման մեջ n քանակի օղակաձև կանգնած զինվորներից սպանում են յուրաքանչյուր m-րդին։ Հարկավոր է գտնել վերջինը մնացող զինվորի k նախնական դիրքը։

Ռեկուրենտ հարաբերությունները

Եթե հայտնի է խնդրի լուծումը զինվորների որոշակի քանակի դեպքում, ապա հնարավոր է դա օգտագործել մեկով ավելի զինվորի պայմանով լուծման համար։

$m=2$-ի համար ունենք

$k(n)={\begin{cases}1,&{\mbox{if }}n=1\\1+(k(n-1)+1)\mod {n},&{\mbox{if }}n>1\end{cases}}$.

$m=3$-ի համար ունենք

$k(n)={\begin{cases}1,&{\mbox{if }}n=1\\1+(k(n-1)+2)\mod {n},&{\mbox{if }}n>1\end{cases}}$.

Ակնհայտ է, որ ընդհանուր դեպքի համար կունենանք՝

$\forall m>0:k(n,m)={\begin{cases}1,&{\mbox{if }}n=1\\1+(k(n-1,m)+m-1)\mod {n},&{\mbox{if }}n>1\end{cases}}$.

Հնարավոր է ռեկուրենտ հարաբերությունների կառուցումը, որոնք համընկնում են շատ ավելի արագ, քան գծայինները։ Ահա լուծման ձև $m=2$-ի համար ռեկուրսիայի լոգարիթմական քայլի թվով։

$k(n)={\begin{cases}1,&{\mbox{if }}n=1\\2k\left({\frac {n}{2}}\right)-1,&{\mbox{if }}n>1{\mbox{ is even}}\\2k\left({\frac {n-1}{2}}\right)+1,&{\mbox{if }}n>1{\mbox{ is odd}}\end{cases}}$։

Գրականություն

• М. А. Алексеев, Задача Иосифа Флавия, Империя Математики, 2001, էջ 22-28
• Дональд Кнут, Роналд Грэхем, Орен Паташник, Конкретная математика. Основание информатики, Мир, 2006, էջեր 703 5-94774-560-7