موضوع مقاله: مسئله ۱۰۰ زندانی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مسئله ۱۰۰ زندانی | مقدمه: در این مسئله، ۱۰۰ زندانی شماره‌دار باید شماره‌ی خود را در یکی از ۱۰۰ کشو پیدا کنند تا زنده بمانند. | ## بخش 1: مسئله ۱۰۰ زندانی | قوانین بیان می‌کنند که هر زندانی تنها مجاز است ۵۰ کشو را باز کند و نمی‌تواند با زندانیان دیگر ارتباط برقرار کند. در نگاه اول، این وضعیت کاملاً ناامیدکننده به نظر می‌رسد؛ اما یک استراتژی هوشمندانه به زندانیان شانس واقعی برای نجات می‌دهد. پیتر برو میلترسن، دانشمند دانمارکی، برای اولین بار در سال ۲۰۰۳ استراتژی ای برای این مسئله ارائه کرد که شانس خوبی برای نجات یافتن همهٔ زندانی‌ها باشد. نسخه‌ی زیر از فیلیپ فلاژولت و رابرت سجویک است:رئیس زندان به ۱۰۰ زندانی محکوم به اعدام که شماره‌هایشان از ۱ تا ۱۰۰ است، یک فرصت آخر می‌دهد. رئیس زندان به‌صورت تصادفی شماره‌ی هر زندانی را در یکی از کشوهای بسته قرار می‌دهد. هر زندانی می‌تواند ۵۰ کشو را به ترتیب دلخواه باز کرده و شماره‌ی داخل آن‌ها را نگاه کند. اگر طی این جست‌وجو هر زندانی شماره‌ی خود را در یکی از کشوها پیدا کند، همه‌ی زندانیان بخشیده می‌شوند. قبل از اینکه اولین زندانی وارد اتاق شود، زندانیان می‌توانند با هم درباره‌ی استراتژی صحبت کنند؛ اما پس از ورود اولین زندانی، هیچ ارتباطی مجاز نیست. بهترین استراتژی زندانیان چیست؟اگر یک زندانی ۵۰ کشو را با هم به صورت تصادفی انتخاب کند، به احتمال ۵۰٪ عددش در ۵۰ کشویی است که انتخاب کرده و در نتیجه احتمال اینکه همه نجات یابند برابر است با ؛ که عددی بسیار کوچک و تقریباً نزدیک به صفر است. استراتژی اصلی در این استراتژی ما ۵۰ کشو را با هم انتخاب نمی‌کنیم و از اطلاعاتی که با باز کردن کشو به دست می‌آوریم استفاده می‌کنیم. | ## بخش 2: مسئله ۱۰۰ زندانی | زندانی شمارهٔ n اُم، ابتدا کشوی شمارهٔ n اُم را باز می‌کند اگر عدد درون آن n بود، پس او نجات یافته‌است؛ اگر نه، پس از آن کشویی که شمارۀ آن برابر با شمارۀ درون کشو است را باز می‌کنیم. این عملیات را تا زمانی که ۵۰ کشو را انتخاب کرده باشیم ادامه می‌دهیم؛ اگر در حین عملیات به n برسد زندانی نجات می‌یابد. زندانی شمارۀ ۲ کشوی شمارۀ ۲، ۴ و سپس ۸ را باز می‌کند و در کشوی شمارۀ ۸، شمارۀ خود را می‌بیند و نجات می‌یابد. زندانی شمارۀ ۳ کشوی شمارۀ ۳ و ۶ را باز می‌کند و در کشوی شمارۀ ۶، شمارۀ خود را می‌بیند و نجات می‌یابد. زندانی شمارۀ ۴ کشوی شمارۀ ۴، ۸ و سپس ۲ را باز می‌کند و در کشوی شمارۀ ۲، شمارۀ خود را می‌بیند و نجات می‌یابد. در نتیجه عدد اولی که زندانی i انتخاب می‌کند، راس متصل به i در گراف جایگشت آن جایگشت است. در نتیجه اگر تمام دور‌های گراف طولشان کمتر از ۵۰ باشد، همه نجات می‌یابند؛ یا به عبارت دیگر اگر طول ماکسیمم دور گراف کمتر مساویِ ۵۰ باشد همه نجات می‌یابند. احتمال اینکه ماکسیمم دور بزرگتر از ۵۰ باشد برابر است با در نتیجه احتمال اینکه ماکسیمم دور کمتر مساویِ ۱۰۰ باشد برابر است با که در آن عدد n اُم سری هارمونیک است. پس می بینیم به طرز شگفت‌آوری در ۳۱٪ مواقع همۀ زندانی‌ها با این استراتژی نجات می‌یابند. احتمال نجات یافتن همه در حالت کلی حالا اگر به جای ۱۰۰ عدد دلخواه 2n را بگذاریم احتمال نجات یافتن همه با استراتژی اصلی برابر است با: با استفاده از ثابت اویلر-ماسکرونی در معادله به این صورت ساده می‌شود: پس از آنجایی که معادله نزولی است به ازای هر n بیش از ۳۰٪ احتمال دارد که همه نجات یابند. | ## بخش 3: مسئله ۱۰۰ زندانی | اول یک بازی جدید به نام بازی ۲ را این‌گونه تعریف می‌کنیم: نفر اول می‌آید و آنقدر کشو باز می‌کند تا به شماره ی ۱ برسد. سپس فردی که کوچک‌ترین شماره‌ای که نفر اول برنداشته را دارد، می‌آید و همین کار را انجام می‌دهد و این روند ادامه پیدا می‌کند. حالا وقتی تمام ۱۰ کشو باز شد، ۱۰ عدد انتخاب شده تشکیل یک جایگشت از اعداد ۱ تا ۱۰ می‌دهند؛ مثلاً ۲٬۶٬۱٬۴٬۹٬۷٬۱۰٬۸٬۳٬۵. حالا احتمال اینکه نفر اول کشوی شامل ۲ را انتخاب کند برابر است با و همین‌طور احتمال اینکه بعد آن ۱۰ را انتخاب کند برابر است با . حال اثبات می‌کنیم هر دسته‌بندی به این شکل را می‌توان با دور های یک گراف جایگشت، تناظر یک به یک داد. اثبات: دور های یک گراف جایگشت را در نظر بگیرید، اعداد هر دور را طوری بچرخانید که عدد مینیمم آخر قرار بگیرد و دورها را به ترتیب مینیمم‌هایشان مرتب کنید. این معادل یک دسته‌بندی از بازی ۲ می‌شود مثال: (۲٬۴٬۶ ۱٬۳٬۱۰٬۵ ۹٬۷٬۸) -> (۸٬۹٬۷ ۴٬۶٬۲ ۳٬۱۰٬۵٬۱) = ۷ ۹ ۸ ۲ ۶ ۴ ۱ ۵ ۱۰ ۳ پس نتیجه می‌گیریم احتمال اینکه در بازی دوم پیروز شویم برابر با احتمال این است که گراف دور بزرگتر از ۵ نداشته باشد که احتمال آن در بالا محاسبه شده‌است. هر کاری که یک زندانی در این استراتژی انجام می‌دهد را می‌تواند در بازی دوم هم انجام دهد و اگر نفر قبل از او یک کشو را باز کرده بود، دیگر لازم نیست او نیز همان کشو را باز کند. | ## جمع‌بندی | در نتیجه احتمال اینکه به ازای هر استراتژی بتوان بازی اول را برد، کمتر از احتمال بردن بازی دوم است (که مستقل از استراتژی است).