مسئله ۱۰۰ زندانی کیست؟ توضیح بده.
مسئله‌ی ۱۰۰ زندانی یک مسئله‌ی ریاضی در نظریه‌ی احتمالات و ترکیبیات است. در این مسئله، ۱۰۰ زندانی شماره‌دار باید شماره‌ی خود را در یکی از ۱۰۰ کشو پیدا کنند تا زنده بمانند. قوانین بیان می‌کنند که هر زندانی تنها مجاز است ۵۰ کشو را باز کند و نمی‌تواند با زندانیان دیگر ارتباط برقرار کند. در نگاه اول، این وضعیت کاملاً ناامیدکننده به نظر می‌رسد؛ اما یک استراتژی هوشمندانه به زندانیان شانس واقعی برای نجات می‌دهد.آنا گال و پیتر برو میلترسن این مسئله را برای اولین بار در سال ۲۰۰۳ مطرح کردند.پیتر برو میلترسن، دانشمند دانمارکی، برای اولین بار در سال ۲۰۰۳ استراتژی ای برای این مسئله ارائه کرد که شانس خوبی برای نجات یافتن همهٔ زندانی‌ها باشد.شرح مسئله.مسئله‌ی ۱۰۰ زندانی نسخه‌های مختلفی در ادبیات دارد. نسخه‌ی زیر از فیلیپ فلاژولت و رابرت سجویک است:رئیس زندان به ۱۰۰ زندانی محکوم به اعدام که شماره‌هایشان از ۱ تا ۱۰۰ است، یک فرصت آخر می‌دهد. اتاقی وجود دارد که در آن یک کمد با ۱۰۰ کشو قرار دارد. رئیس زندان به‌صورت تصادفی شماره‌ی هر زندانی را در یکی از کشوهای بسته قرار می‌دهد. زندانیان یکی پس از دیگری وارد اتاق می‌شوند. هر زندانی می‌تواند ۵۰ کشو را به ترتیب دلخواه باز کرده و شماره‌ی داخل آن‌ها را نگاه کند. پس از آن کشوها دوباره بسته می‌شوند. اگر طی این جست‌وجو هر زندانی شماره‌ی خود را در یکی از کشوها پیدا کند، همه‌ی زندانیان بخشیده می‌شوند. اما اگر حتی یک زندانی شماره‌ی خود را پیدا نکند، همه‌ی زندانیان اعدام می‌شوند. قبل از اینکه اولین زندانی وارد اتاق شود، زندانیان می‌توانند با هم درباره‌ی استراتژی صحبت کنند؛ اما پس از ورود اولین زندانی، هیچ ارتباطی مجاز نیست. بهترین استراتژی زندانیان چیست؟اگر یک زندانی ۵۰ کشو را با هم به صورت تصادفی انتخاب کند، به احتمال ۵۰٪ عددش در ۵۰ کشویی است که انتخاب کرده و در نتیجه احتمال اینکه همه نجات یابند برابر است با formula_1؛ که عددی بسیار کوچک و تقریباً نزدیک به صفر است. به نظر می‌رسد که وضعیت کاملاً ناامیدکننده است.استراتژی اصلی.در این استراتژی ما ۵۰ کشو را با هم انتخاب نمی‌کنیم و از اطلاعاتی که با باز کردن کشو به دست می‌آوریم استفاده می‌کنیم.اول کشوها را به ترتیب ۱ تا ۱۰۰ شماره‌گذاری می‌کنیم.زندانی شمارهٔ n اُم، ابتدا کشوی شمارهٔ n اُم را باز می‌کند اگر عدد درون آن n بود، پس او نجات یافته‌است؛اگر نه، پس از آن کشویی که شمارۀ آن برابر با شمارۀ درون کشو است را باز می‌کنیم.این عملیات را تا زمانی که ۵۰ کشو را انتخاب کرده باشیم ادامه می‌دهیم؛ اگر در حین عملیات به n برسد زندانی نجات می‌یابد.مثال.فرض کنید اعداد درون کشوها این‌گونه باشند:در استراتژی ما، هر زندانی این کارها را انجام می‌دهد:در مثال بالا، همه شمارۀ خود را پیدا کردند؛ اما همیشه اینطور نیست. مثلاً فرض کنید اعداد درون کشو ها این‌گونه باشد:در این مثال، زندانی اول کشوهای ۱، ۳، ۷ و ۴ را باز می‌کند؛ اما شمارۀ خود را در آن پیدا نمی‌کند. ولی زندانی شمارۀ ۶، شمارۀ خود را در اولین کشویی که باز می‌کند، می‌یابد.احتمال نجات یافتن همه.اعداد درون این کشو ها در واقع جایگشتی از اعداد ۱ تا ۱۰۰ است. در نتیجه عدد اولی که زندانی i انتخاب می‌کند، راس متصل به i در گراف جایگشت آن جایگشت است. پس اگر دوری که راس i اُم در آن است کوچکتر از ۵۰ باشد، زندانی نجات می‌یابد.در نتیجه اگر تمام دور‌های گراف طولشان کمتر از ۵۰ باشد، همه نجات می‌یابند؛ یا به عبارت دیگر اگر طول ماکسیمم دور گراف کمتر مساویِ ۵۰ باشد همه نجات می‌یابند.اگر formula_2 باشد، تعداد گراف‌هایی که طول بزرگ‌ترین دور آن ۵۰ است برابر است با:formula_3اثبات.اگر formula_4 باشد و formula_5 راس از رئوس گراف را انتخاب کنیم، طول بزرگترین دور گراف برابر formula_5 خواهد بود، چون تعداد بقیۀ رأس‌ها از ۵۰ کمتر استحال formula_5 تا از رأس‌ها را انتخاب می‌کنیم، formula_8 تا از گراف‌ها از formula_5 راسی که انتخاب کردیم تشکیل یک دور می‌دهند. formula_10 راس باقی‌مانده هم تشکیل یک گراف می‌دهند؛ پس formula_11 حالت برای بقیۀ رأس‌ها موجود است.احتمال اینکه ماکسیمم دور بزرگتر از ۵۰ باشد برابر است باformula_12در نتیجه احتمال اینکه ماکسیمم دور کمتر مساویِ ۱۰۰ باشد برابر است باformula_13که در آن formula_14 عدد n اُم سری هارمونیک است.پس می بینیم به طرز شگفت‌آوری در ۳۱٪ مواقع همۀ زندانی‌ها با این استراتژی نجات می‌یابند.احتمال نجات یافتن همه در حالت کلی.حالا اگر به جای ۱۰۰ عدد دلخواه 2n را بگذاریم احتمال نجات یافتن همه با استراتژی اصلی برابر است با:با استفاده از ثابت اویلر-ماسکرونی formula_16 در formula_17معادله به این صورت ساده می‌شود:پس از آنجایی که معادله نزولی است به ازای هر n بیش از ۳۰٪ احتمال دارد که همه نجات یابند.بهینگی.ما بهینگی روش گفته شده را برای سادگی برای formula_19. ثابت می‌کنیم و به ازای n های دیگر اثبات مشابه دارد.اول یک بازی جدید به نام بازی ۲ را این‌گونه تعریف می‌کنیم: نفر اول می‌آید و آنقدر کشو باز می‌کند تا به شماره ی ۱ برسد. سپس فردی که کوچک‌ترین شماره‌ای که نفر اول برنداشته را دارد، می‌آید و همین کار را انجام می‌دهد و این روند ادامه پیدا می‌کند. حالا اگر یک نفر بیش از ۵ کشو باز کند بازی را باخته‌ایم.حالا وقتی تمام ۱۰ کشو باز شد، ۱۰ عدد انتخاب شده تشکیل یک جایگشت از اعداد ۱ تا ۱۰ می‌دهند؛ مثلاً ۲٬۶٬۱٬۴٬۹٬۷٬۱۰٬۸٬۳٬۵. حالا احتمال اینکه نفر اول کشوی شامل ۲ را انتخاب کند برابر است با formula_20 و همین‌طور احتمال اینکه بعد آن ۱۰ را انتخاب کند برابر است با formula_21. در نتیجه احتمال اینکه هر جایگشت دلخواه انتخاب شود، برابر formula_22 است. در نتیجه پیروزی در بازی دوم مستقل از استراتژی است.حال همۀ اعدادی که یک نفر انتخاب کرده را در یک دسته قرار می‌دهیم. برای مثال ارائه شده در بالا این‌گونه می‌شود: (۵)(۴٬۹٬۷٬۱۰٬۸٬۳)(۲٬۶٬۱). حال اثبات می‌کنیم هر دسته‌بندی به این شکل را می‌توان با دور های یک گراف جایگشت، تناظر یک به یک داد. اثبات: دور های یک گراف جایگشت را در نظر بگیرید، اعداد هر دور را طوری بچرخانید که عدد مینیمم آخر قرار بگیرد و دورها را به ترتیب مینیمم‌هایشان مرتب کنید. این معادل یک دسته‌بندی از بازی ۲ می‌شودمثال: (۲٬۴٬۶)(۱٬۳٬۱۰٬۵)(۹٬۷٬۸) -&gt; (۸٬۹٬۷)(۴٬۶٬۲)(۳٬۱۰٬۵٬۱) = ۷ ۹ ۸ ۲ ۶ ۴ ۱ ۵ ۱۰ ۳پس نتیجه می‌گیریم احتمال اینکه در بازی دوم پیروز شویم برابر با احتمال این است که گراف دور بزرگتر از ۵ نداشته باشد که احتمال آن در بالا محاسبه شده‌است.حال یک استراتژی در بازی اول (همان استراتژی اصلی) را در نظر بگیرید. هر کاری که یک زندانی در این استراتژی انجام می‌دهد را می‌تواند در بازی دوم هم انجام دهد و اگر نفر قبل از او یک کشو را باز کرده بود، دیگر لازم نیست او نیز همان کشو را باز کند. در هر استراتژی ای که با آن بازی اول را بتوان برد، بازی دوم را هم می‌توان برد.در نتیجه احتمال اینکه به ازای هر استراتژی بتوان بازی اول را برد، کمتر از احتمال بردن بازی دوم است (که مستقل از استراتژی است). در نتیجه استراتژی ای که ارائه کردیم بهترین استراتژی است.