سخت ترین سوالات ریاضی که برای حل آنها پاداش در نظر گرفته شده است ممکن در نگاه اول بسیار ساده به نظر بیایند؛ مسئله ژوزفوس بدنام یکی از همین دست مسائل در دنیای ریاضیات به شمار می رود.
این مسئله اسم خود را از نام تایتوس فلاویس ژوزفوس1 برگرفته که یک محقق یهودی در قرن اول بوده است. موضوع این مسئله از این قرار است که وقتی او توسط لشگر رم محاصره شده، با خود ۴۰ سرباز داشته است و سربازان به جای تسلیم شدن تصمیم گرفتند خودکشی دسته جمعی انجام دهند و این کار را به صورتی انجام دادند که افراد یکدیگر را می کشتند و هیچ کس خودکشی نمی کرد و این تصمیم را از آن جهت گرفتند تا مبادا در لحظات آخر فردی تصمیمش عوض شود و دست به خودکشی نزند.
آنها یک حلقه زدند و اولین سرباز می بایست فرد سمت چپ خود را می کشت و سرباز زنده بعدی نیز باید فرد سمت چپ خود را می کشت و این رویه در کل حلقه باید ادامه پیدا می کرد.
وقتی حلقه مرگ به ابتدای شروع این کار می رسید، این فرایند می بایست با تعداد کمتری از افراد مجددا انجام می گرفت و در نهایت آخرین فردی که زنده می ماند می بایست با شمشیر خودش، به زندگی خود پایان می داد.
در این بین ژوزفوس مشکلی داشت و مشکل این بود که او ترجیح می داد زنده بماند تا مثل بقیه به زندگی خود پایان دهد ولی از قراری که با بقیه سربازان نیز گذاشته بود گریزی نبود و در عین حال نیز نمی خواست هم رزمان خود از راز او مطلع شوند. به نظر شما او باید خود را در کدام قسمت این حلقه قرار می داد تا آخرین فردی باشد که هنوز زنده است؟
جواب جایگاه نوزدهم است. اما اینکه چطور به این عدد رسیدید و اینکه با تعداد مختلف سربازارن به چه عددی می رسید مهم است؛ این دقیقا کاری است که دنیل ارمان از دانشگاه ویسکانسین آن را تشریح کرده است.
در دور اول این حلقه مشخص است هر فردی که در وضعیت جایگاه فرد قرار داشته باشد جان سالم به در برده است پس اگر می خواهید زنده بمانید در این دور، حتما در جایگاه های فرد قرار بگیرید.
اما با شروع دور دوم و نفرات باقی مانده، افرادی که در جایگاه های زوج قرار گرفته اند همچنان سرنوشت مرگباری خواهند داشت.
الگوی مهمی که در این مسئله باید به آن توجه کنیم، این است که اگر تعداد سربازان دقیقاً توانی از ۲ باشند (۲،۴،۸،۱۶،۳۲،۶۴و…..) جایگاه امنی که می توان در آن قرار گرفت همان جایگاه اول است چرا که همیشه شروع کننده حلقه مرگ او است. به مثال زیر توجه کنید:
دو نفر را در نظر بگیرید : فرد شماره ۱ قاعدتاً فرد شماره ۲ را می کشد.
۴ نفر را در نظر بگیرید: فرد شماره ۱، شماره ۲ را می کشد و فرد شماره ۳ شماره ۴ را می کشد و فرد شماره ۱ مجدد فرد شماره ۳ را می کشد. وقتی تعداد نفرات توانی از ۲ باشند فرقی نمی کند که چه تعداد باشند چرا که فرد شماره یک همواره شروع کننده کشتار است.
توانی از دو بودن تعداد، کلید اصلی این مسئله است. حال با توجه به شرایط موجود بگویید، چند فرد باید باقی بمانند تا شما بتوانید جان خود را نجات دهید؟
جواب: این تعداد که باید باقی بمانند با حرف l در فرمول نهایی نشان داده شده و جایگاهی که باید در آن قرار گیرید تا جان سالم به در ببرید ۱+(۲*l) است.
بنابراین ژوزفوس باید در جایگاه نوزدهم قرار گیرد تا جان سالم به در ببرد چرا که نزدیک ترین عدد به ۴۰ که توانی از ۲ است، عدد ۳۲ است و با حساب فرمول نهایی در دور آخر ۹ فرد باقی می مانند و اگر ۹ را در فرمول (۲*۹) +۱ قرار دهیم عدد ۱۹ به دست می آید که به ما می گوید اگر او از ابتدا در جایگاه ۱۹ قرار گیرد مطمئنا زنده خواهد ماند. ژوزفوس با این حربه تا رسیدن به اولین توان ۲ حلقه ها (در این مثال ۳۲) همواره نفر اول می ماند.
1. Titus Flavius Josephus
/**
*
* @param n the number of people standing in the circle
* @return the safe position who will survive the execution
* f(N) = 2L + 1 where N =2^M + L and 0 <= L < 2^M
*/
public int getSafePosition(int n) {
// find value of L for the equation
int valueOfL = n - Integer.highestOneBit(n);
int safePosition = 2 * valueOfL + 1;
return safePosition;
}