مسئله ۱۰۰ زندانی
۱۰۰ عدد زندانی موجودند که شماره‌های ۱ تا ۱۰۰ دارند و ۱۰۰ تا کشو وجود دارد که درون هر کدام یکی از اعداد ۱ نا ۱۰۰ وجود دارد هر زندانی می‌تواند بدون اینکه با دیگر زندانی‌ها صحبت کند ۵۰ تا از این کشوها را باز کند. در صورتی جان سالم به در می‌برند که همه زندانی‌ها شماره‌های خود را پیدا کرده باشند (اگر حتی یک نفر شماره خود را پیدا نکند همه زندانی خواهند ماند). دانشمندی دانمارکی به نام پیتر برو میلترسون برای اولین بار در سال ۲۰۰۳ استراتژی ای برای این مسئله ارائه کردند که شانس خوبی برای نجات یافتن همهٔ زندانی‌ها باشد.
اگر یک زندانی ۵۰ کشو را با هم به صورت رندوم انتخاب کند به احتمال ۵۰٪ عددش در ۵۰ کشویی است که انتخاب کرده در نتیجه احتمال اینکه همه نجات یابند برابر است با:
(½) ≈ 0.0000000000000000000000000000008 در این استراتژی ما ۵۰ کشو را با هم انتخاب نمی‌کنیم و از اطلاعات ای که با باز کردن کشو به دست می‌آوریم استفاده می‌کنیم. اول کشوها را به ترتیب ۱ تا ۱۰۰ شماره‌گذاری می‌کنیم. سپس زندانی شمارهٔ i ام کشوی شمارهٔ i ام را اول باز می‌کند اگر عدد درون آن i بود پس او نجات یافته‌است. اگر نه کشوای که شمارهٔ ان برابر با شمارهٔ درون کشو است را باز می‌کنیم. این عملیات را تا زمانی که ۵۰ کشو را انتخاب کرده باشید ادامه می‌دهد اگر در حین عملیات به i برسد زندانی نجات می‌یابد.
فرض کنید اعداد درون کشوها این‌گونه باشند: در استراتژی ما هر زندانی این کارها را انجام می‌دهد: در مثال بالا همه شمارهٔ خود را پیدا کردند اما همیشه اینطور نیست مثلاً فرض کنید اعداد درون کشوها این‌گونه باشد: در این مثال زندانی اول کشوهای ۱ و ۳ و ۷ و۴ را باز می‌کند اما شمارهٔ خود را در آن پیدا نمی‌کند اما زندانی ۶ شمارهٔ خود را در اولین کشویی که باز می‌کند پیدا می‌کند.
اعداد درون این کشوها در واقع جایگشتی از اعداد ۱ تا ۱۰۰ است. در نتیجه عدد اولی که زندانی i انتخاب می‌کند راس متصل به i در گراف جایگشت ان جایگشت است پس اگر دوری که راس i ام در ان است کوچکتر از ۵۰ باشد زندانی نجات می‌یابد. در نتیجه اگر تمام دور‌های گراف طولشان کمتر از ۵۰ باشد همه نجات می‌یابند، یا به عبارت دیگر اگر طول ماکسیمم دور گراف کمتر مساوی ۵۰ باشد همه نجات می‌یابند.
اگر formula_1 تعداد گراف‌هایی که طول بزرگ‌ترین دور ان ۵۰ است برابر است با:
formula_2.
اگر formula_3 و l راس از رئوس گراف را انتخاب کنیم طول بزرگترین دور گراف برابر l خواهد بود چون تعداد بقیهٔ رأس‌ها از ۵۰ کمتر است حال l تا از رأس‌ها را انتخاب می‌کنیم formula_4 تا از گراف‌ها از l راسی که انتخاب کردیم تشکیل یک دور می‌دهند formula_5 راس باقی‌مانده هم تشکیل یک گراف می‌دهند پس formula_6 حالت برای بقیهٔ رأس‌ها موجود است. احتمال اینکه ماکسیمم دور بزرگتر از ۵۰ باشد برابر است با
formula_7 در نتیجه احتمال اینکه ماکسیمم دور کمتر مساوی ۱۰۰ باشد برابر است با
formula_8،
که در ان formula_9 عدد n ام سری هارمونیک است. پس دیدم به طرز شگفت‌آوری در ۳۱٪ مواقع همهٔ زندانی‌ها با این استراتژی نجات می‌یابند.
حالا اگر به جای ۱۰۰ عدد دلخواه 2n را بگذاریم احتمال نجات یافتن همه با استراتژی اصلی برابر است با:
با استفاده از ثابت اویلر-ماسکرونی formula_11 در formula_12 معادله به این صورت ساده می‌شود:
پس از آنجایی که معادله نزولی است به ازای هر n بیش از ۳۰٪ احتمال دارد که همه نجات یابند.
ما بهینگی روش گفته شده را برای سادگی برای formula_14. ثابت می‌کنیم و به ازای nهای دیگر اثبات مشابه دارد. اول یک بازی جدید به نام بازی ۲ را این‌گونه تعریف می‌کنیم نفر اول می‌آید و آنقدر کشو باز می‌کند تا به شمارهٔ ۱ برسد بعد فردی که کوچک‌ترین شماره‌ای که نفر اول برنداشته را دارد می‌آید و همین کار را می‌کند و این روند ادامه پیدا می‌کند. حالا اگر یک نفر بیش از ۵ کشو باز کند بازی را باخته‌ایم. حالا وقتی تمام ۱۰ کشو باز شد ۱۰ عدد انتخاب شده تشکیل یک جایگشت از اعداد ۱ تا ۱۰ می‌دهند مثلاً ۲٬۶٬۱٬۴٬۹٬۷٬۱۰٬۸٬۳٬۵ حالا احتمال اینکه نفر اول کشوی شامل ۲ را انتخاب کند برابر است با formula_15 و همین‌طور احتمال اینکه بعد آن ۱۰ را انتخاب کند برابر است با formula_16 در نتیجه احتمال اینکه هر جایگشت دلخواه انتخاب شود برابر formula_17 است. در نتیجه پیروزی در بازی دوم مستقل از استراتژی است حال همهٔ اعدادی که یک نفر انتخاب کرده را در یک دسته قرار می‌دهیم برای مثال ارائه شده در بالا این‌گونه می‌شود: (۵)(۴٬۹٬۷٬۱۰٬۸٬۳)(۲٬۶٬۱) حال اثبات می‌کنیم هر دسته‌بندی این شکلی را می‌توان با دورهای یک گراف جایگشت تناظر یک به یک داد. اثبات: دورهای یک گراف جایگشت را در نظر گیرید اعداد هر دور را طوری بچرخانید که عدد مینیمم آخر قرار گیرد و دورها را به ترتیب مینیمم‌هایشان مرتب کنید این معادل یک دسته‌بندی از بازی ۲ می‌شود مثال: (۲٬۴٬۶)(۱٬۳٬۱۰٬۵)(۹٬۷٬۸) -> (۸٬۹٬۷)(۴٬۶٬۲)(۳٬۱۰٬۵٬۱) = ۷ ۹ ۸ ۲ ۶ ۴ ۱ ۵ ۱۰ ۳ پس نتیجه می‌گیریم که احتمال اینکه در بازی دوم پیروز شویم برابر با احتمال این است که گراف دور بزرگتر از ۵ نداشته باشئ که احتمال ان در بالا محاسبه شده‌است. حال یک استراتژی در بازی اول (همان استراتژی اصلی) را در نظر بگیرید هر کاری که یک زندانی در این استراتژی انجام می‌دهد می‌تواند در بازی دوم انجام دهد و اگر نفری قبل از او یک کشو را باز کرده بود دیگر لازم نیست باز کند در هر استراتژی ای که با آن بازی اول را بتوان برد بازی دوم هم می‌توان برد. در نتیجه احتمال اینکه به ازای هر استرتژی بتوان بازی اول را برد کمتر از احتمال بردن بازی دوم است (که مستقل از استراتژی است) در نتیجه استراتژی ای که ارائه کردیم بهترین استراتژی است.
Wikipedia contributors, "100 Prisoners Problem " Wikipedia, The Free Encyclopedia, https://en.wikipedia.org/wiki/100_prisoners_problem