تاريخچه

اين مساله منتسب به فلاويوس ژوزفوس يك تاريخدان يهودي قرن اول ميلادي است. آنگونه كه داستان مي گويد، او و 40 سرباز همراه وي در يك غار زنداني شده اند كه توسط رومي ها محاصره شده است. آنها خودكشي را بر اسير شدن ترجيح مي دهند و تصميم مي گيرند كه يك دايره را تشكيل داده و سه تا سه تا خود را بكشند. چون ژوزفوس نمي خواهد كشته شود، و مي تواند مكان امن دور دايره را پيدا كند با يكي از همراهانش زنده مي ماند و به روميها كه آنها را دستگير مي كنند، مي پيوندد.(تنها جمله اي كه ژوزفوس بعدا گفت، اين بود كه با خوش شانسي يا به ياري لطف خدا او و فرد ديگري باقي ماندند و تسليم رومي ها شدند)


راه حل

ما مساله را درحالتي حل ميكنيم كه افراد دوتا دوتا كشته شوند:k=2.(براي حالت كلي تر يك راه حل نشان خواهيم داد). راه حل را به صورت روابط بازگشتي ارائه مي دهيم. فرض كنيد (f(n، مكان نجات يابنده باشد در صورتيكه n تعداد اوليه افراد باشد و (k=2). در اولين گردش دور دايره، تمام افراد با شماره زوج مي ميرند. در دومين چرخش، افراد جديد دوم كشته مي شوند و در دور بعدي افراد جديد چهارم و الي آخر .

اگر تعداد افراد اوليه زوج باشد، آنگاه فردي كه در دور دوم در مكان x‌ قرار گرفته است ابتدا در مكان 2x-1 بوده است. بنابراين فردي كه در مكان(f(n ‌قرار دارد، ابتدا در مكان 2f(n)-1 بوده است. اين ايده چنين رابطه بازگشتي را به ما ميدهد:

f(2n)=2f(n)-1

اگر تعداد افراد اوليه فرد باشد، آنگاه فرد شماره يك در اولين دور كشته خواهد شد. دوباره در دور دوم، افراد زوج جديد كشته خواهند شد. و در دور بعدي افراد چهارم جديد. اين ايده نيز به چينن رابطه اي بازگشتي اي منجر مي گردد: f(2n+1)=2f(n)+1

وقتي مقادير n و (f(n را جدول بندي كنيم چنين الگويي را مشاهده ميكنيم:

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

f(n) 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1

اين الگو نشان مي دهد كه (f(n يك دنباله فرد صعودي است كه از f(n)=1 شروع مي شود؛ وقتي كه انديس n تواني از 2 باشد. بنابراين اگر m و l را به گونه اي انتخاب كنيم كه n = 2m + l و 0\leq l<2^m باشد و آنگاه f(n)=2l+1. اين واضح است كه مقادير در جدول اين معادله را ارضا ميكنند. اما رياضيات نيازمند اثبات قطعي است. در زير ما اثباتي را از طريق استقرا ارائه ميكنيم.

قضيه: اگرn = 2m + l و0\leq l<2^m،آنگاه f(n)=2l+1


اثبات: ما از استقراي رياضي قوي روي n‌ استفاده مي كنيم. پايه n=1‌ است كه درست است.ما n هاي فرد و زوج را جداگانه بررسي مي نماييم. اگر n زوج باشد، آنگاه ماl1وm1 را انتخاب ميكنيم به گونه اي كهn/2 = 2^{m_1}+l_1 و 0\leq l_1 < 2^{m_1}. توجه داشته باشيد كه l_1=\frac{1}{2}.داريم

f(n)=2f(\frac{n}{2})-1=2(2l_1+1)-1=2l+1

كه تساوي دوم از فرض استقرا به دست مي آيد.

حال اگر n فرد باشد ماm1 وl1 را به گونه اي انتخاب مي كنيم كه\frac{n-1}{2} = 2^{m_1}+l_1 و 0\leq l_1 < 2^{m_1}. توجه داشته باشيد كه l_1=\frac{l}{2}.داريم f(n) = 2f(\frac {n-1}{2}) + 1 = 2((2l_1) + 1) + 1 = 2l + 1 كه تساوي دوم از فرض استقرا به دست مي آيد. و اثبات كامل مي شود.

ظريف ترين شكل جواب نمايش دودويي n را دربرمي گيرد كه توسط آقای "آرمین شمس براق" دانشجوی دانشگاه مشهد به صورت زیر پیشنهاد شده و مورد توجه طراحانالگوریتم برجسته دنیا قرار گرفته است : اگر n را بصورت باینری بنویسیم و شماره فردی که زنده می ماند را برابر Jn بگیریم , و n را یک بیت شیفت دوران دهیم Jn به دست می‌آید.