مسئله ۱۰۰ زندانی

در مسئله‌ی 100 زندانی هر زندانی فقط ۵۰ کشو را می‌تواند باز کند
۱۰۰ عدد زندانی موجودند که شماره‌های ۱ تا ۱۰۰ دارند و ۱۰۰ تا کشو وجود دارد که درون هر کدام یکی از اعداد ۱ نا ۱۰۰ وجود دارد هر زندانی می‌تواند بدون اینکه با دیگر زندانی‌ها صحبت کند ۵۰ تا از این کشوها را باز کند. در صورتی جان سالم به در می‌برند که همه زندانی‌ها شماره‌های خود را پیدا کرده باشند(اگر حتی یک نفر شماره خود را پیدا نکند همه زندانی خواهند ماند). دانشمندی دانمارکی به نام پیتر برو میلترسون برای اولین بار در سال ۲۰۰۳ استراتژی‌ای برای این مسئله ارائه کردند که شانس خوبی برای نجات یافتن همه زندانی‌ها باشد.
رندوم برداشتن کشوها
اگر یک زندانی ۵۰ کشو را با هم به صورت رندوم انتخاب کند به احتمال ۵۰٪ عددش در ۵۰ کشویی است که انتخاب کرده در نتیجه احتمال اینکه همه نجات یابند برابر است با:
(1⁄2) 100 ≈ 0.0000000000000000000000000000008
استراتژی اصلی
در این استراتژی ما ۵۰ کشو را با هم انتخاب نمی‌کنیم و از اطلاعات ای که با باز کردن کشو به دست می‌آوریم استفاده می‌کنیم.
اول کشوها را به ترتیب ۱ تا ۱۰۰ شماره‌گذاری می‌کنیم.
سپس زندانی شماره i ام کشوی شماره i ام را اول باز می‌کند اگر عدد درون آن i بود پس او نجات یافته‌است.
اگر نه کشوای که شماره ان برابر با شماره درون کشو است را باز می‌کنیم.
این عملیات را تا زمانی که ۵۰ کشو را انتخاب کرده باشید ادامه می‌دهد اگر در حین عملیات به i برسد زندانی نجات می‌یابد.
مثال
فرض کنید اعداد درون کشوها این‌گونه باشند:
شماره‌ی کشو
1
2
3
4
5
6
7
8
شماره‌ی زندانی
7
4
6
8
1
3
5
2
در استراتژی ما هر زندانی این کارها را انجام می‌دهد:
زندانی 1 کشو ی شماره‌ی 1 را باز می‌کند بعد در ان 7 را می‌بیند. بعد کشو ی شماره‌ی 7 را باز می‌کند بعد در ان 5 را می‌بیند. بعد کشو ی شماره‌ی 5 را باز می‌کند بعد در ان شماره‌ی خود را می‌بیند و نجات می‌یابد.
زندانی 2 کشو ی شماره‌ی 2 و 4و 8 را باز می‌کند بعد در 8 شماره‌ی خود را می‌بیند و نجات می‌یابد.
زندانی 3 کشو ی شماره‌ی 3 و 6 را باز می‌کند بعد در 6 شماره‌ی خود را می‌بیند و نجات می‌یابد.
زندانی 4 کشو ی شماره‌ی 4 و 8و 2 را باز می‌کند بعد در 2 شماره‌ی خود را می‌بیند و نجات می‌یابد.
همینگونه زندانی‌های 5 تا هم شماره‌ی خود را پیدا می‌کنند.
در مثال بالا همه شماره‌ی خود را پیدا کردند اما همیشه اینطور نیست مثلا فرض کنید اعداد درون کشوها این‌گونه باشد:
شماره‌ی کشو
1
2
3
4
5
6
7
8
شماره‌ی زندانی
3
1
7
5
8
6
4
2
در این مثال زندانی اول کشوهای 1 و 3 و 7 و4 را باز می‌کند اما شماره‌ی خود را در آن پیدا نمی‌کند اما زندانی 6 شماره‌ی خود را در اولین کشویی که باز می‌کند پیدا می‌کند.
احتمال نجات یافتن همه
توزیع احتامالاتی بطرگترین دور یک جایگشت رندوم که قسمت سبز نشان دهنده‌ی احتمال نجات یافتن همه است
اعداد درون این کشوها در واقع جایگشتی از اعداد ۱ تا ۱۰۰ است. در نتیجه عدد اولی که زندانی i انتخاب می‌کند راس متصل به i در گراف جایگشت ان جایگشت است پس اگر دوری که راس i ام در ان است کوچکتر از ۵۰ باشد زندانی نجات می‌یابد.
در نتیجه اگر تمام دورهای گراف طولشان کمتر از ۵۰ باشد همه نجات می‌یابند، یا به عبارت دیگر اگر طول ماکسیمم دور گراف کمتر مساوی ۵۰ باشد همه نجات می‌یابند.
اگر تعداد گراف‌هایی که طول بزرگ‌ترین دور ان ۵۰ است برابر است با:
اثبات
سری هارمونیک با مساحت زیر هذلولی نشان داده شده تقریب زده می‌شود که خود با لگاریتم تقریب زده می‌شود
اگر و l راس از رئوس گراف را انتخاب کنیم طول بزرگترین دور گراف برابر l خواهد بود چون تعداد بقیه راس‌ها از ۵۰ کمتر است
حال l تا از راس‌ها را انتخاب می‌کنیم تا از گراف‌ها از l راسی که انتخاب کردیم تشکیل یک دور می‌دهند راس باقی‌مانده هم تشکیل یک گراف می‌دهند پس حالت برای بقیه راس‌ها موجود است.
احتمال اینکه ماکسیمم دور بزرگتر از ۵۰ باشد برابر است با
در نتیجه احتمال اینکه ماکسیمم دور کمتر مساوی ۱۰۰ باشد برابر است با
که در ان عدد n ام سری هارمونیک است.
پس دیدم به طرز شگفت آوری در ۳۱٪ مواقع همه زندانی‌ها با این استراتژی نجات می‌یابند.
احتمال نجات یافتن همه در حالت کلی
حالا اگر به جای ۱۰۰ عدد دلخواه 2n را بگذاریم احتمال نجات یافتن همه با استراتژی اصلی برابر است با:
با استفاده از ثابت اویلر-ماسکرونی در
معادله به این صورت ساده می‌شود:
پس از آنجایی که معادله نزولی است به ازای هر n بیش از ۳۰٪ احتمال دارد که همه نجات یابند.
بهینگی
ما بهینگی روش گفته شده را برای سادگی برای . ثابت می‌کنیم و به ازای n‌های دیگر اثبات مشابه دارد.
اول یک بازی جدید به نام بازی 2 را این‌گونه تعریف می‌کنیم نفر اول می‌اید و انقدر کشو باز می‌کند تا به شماره‌ی 1 برسد بعد فردی که کوچک‌ترین شماره‌ای که نفر اول برنداشته را دارد می‌اید و همین کار را می‌کند و این روند ادامه پیدا می‌کند. حالا اگر یک نفر بیش از 5 کشو باز کند بازی را باخته‌ایم.
حالا وقتی تمام 10 کشو باز شد 10 عدد انتخاب شده تشکیل یک جایگشت از اعداد 1 تا 10 می‌دهند مثلا 2,6،1,4،9,7،10,8،3,5 حالا احتمال اینکه نفر اول کشوی شامل 2 را انتخاب کند برابر است با و همینطور احتمال اینکه بعد آن 10 را انتخاب کند برابر است با در نتیجه احتمال اینکه هر جایگشت دلخواه انتخاب شود برابر است. در نتیجه پیروزی در بازی دوم مستقل از استراتژی است
حال همه اعدادی که یک نفر انتخاب کرده را در یک دسته قرار می‌دهیم برای مثال ارائه شده در بالا این‌گونه می‌شود: (5)(4,9،7,10,8،3)(2,6،1) حال اثبات می‌کنیم هر دسته بندی این شکلی را می‌توان با دورهای یک گراف جایگشت تناظر یک به یک داد. اثبات : دورهای یک گراف جایگشت را در نظر گیرید اعداد هر دور را طوری بچرخانید که عدد مینیمم آخر قرار گیرد و دورها را به ترتیب مینیمم‌هایشان مرتب کنید این معادل یک دسته بندی از بازی 2 می‌شود
مثال: (2,4،6)(1,3،10,5)(9,7،8) -> (8,9،7)(4,6،2)(3,10,5،1) = 7 9 8 2 6 4 1 5 10 3
پس نتیجه می‌گیریم که احتمال اینکه در بازی دوم پیروز شویم برابر با احتمال این است که گراف دور بزرگتر از 5 نداشته باشی که احتمال ان در بالا محاسبه شده‌است.
حال یک استراتژی در بازی اول(همان استراتژی اصلی) را در نظر بگیرید هر کاری که یک زندانی در این استراتژی انجام می‌دهد می‌تواند در بازی دوم انجام دهد و اگر نفری قبل از او یک کشو را باز کرده بود دیگر لازم نیست باز کند در هر استراتژی‌ای که با آن بازی اول را بتوان برد بازی دوم هم می‌توان برد.
در نتیجه احتمال اینکه به ازای هر استرتژی بتوان بازی اول را برد کمتر از احتمال بردن بازی دوم است(که مستقل از استراتژی است) در نتیجه استراتژی‌ای که ارائه کردیم بهترین استراتژی است.