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

در مسئلهٔ ۱۰۰ زندانی هر زندانی فقط ۵۰ کشو را می‌تواند باز کند

مسئله‌ی ۱۰۰ زندانی یک مسئله‌ی ریاضی در نظریه‌ی احتمالات و ترکیبیات است. در این مسئله، ۱۰۰ زندانی شماره‌دار باید شماره‌ی خود را در یکی از ۱۰۰ کشو پیدا کنند تا زنده بمانند. قوانین بیان می‌کنند که هر زندانی تنها مجاز است ۵۰ کشو را باز کند و نمی‌تواند با زندانیان دیگر ارتباط برقرار کند. در نگاه اول، این وضعیت کاملاً ناامیدکننده به نظر می‌رسد؛ اما یک استراتژی هوشمندانه به زندانیان شانس واقعی برای نجات می‌دهد.

آنا گال و پیتر برو میلترسن این مسئله را برای اولین بار در سال ۲۰۰۳ مطرح کردند.

پیتر برو میلترسن، دانشمند دانمارکی، برای اولین بار در سال ۲۰۰۳ استراتژی ای برای این مسئله ارائه کرد که شانس خوبی برای نجات یافتن همهٔ زندانی‌ها باشد.

شرح مسئله

مسئله‌ی ۱۰۰ زندانی نسخه‌های مختلفی در ادبیات دارد. نسخه‌ی زیر از فیلیپ فلاژولت و رابرت سجویک است:

رئیس زندان به ۱۰۰ زندانی محکوم به اعدام که شماره‌هایشان از ۱ تا ۱۰۰ است، یک فرصت آخر می‌دهد. اتاقی وجود دارد که در آن یک کمد با ۱۰۰ کشو قرار دارد. رئیس زندان به‌صورت تصادفی شماره‌ی هر زندانی را در یکی از کشوهای بسته قرار می‌دهد. زندانیان یکی پس از دیگری وارد اتاق می‌شوند. هر زندانی می‌تواند ۵۰ کشو را به ترتیب دلخواه باز کرده و شماره‌ی داخل آن‌ها را نگاه کند. پس از آن کشوها دوباره بسته می‌شوند. اگر طی این جست‌وجو هر زندانی شماره‌ی خود را در یکی از کشوها پیدا کند، همه‌ی زندانیان بخشیده می‌شوند. اما اگر حتی یک زندانی شماره‌ی خود را پیدا نکند، همه‌ی زندانیان اعدام می‌شوند. قبل از اینکه اولین زندانی وارد اتاق شود، زندانیان می‌توانند با هم درباره‌ی استراتژی صحبت کنند؛ اما پس از ورود اولین زندانی، هیچ ارتباطی مجاز نیست. بهترین استراتژی زندانیان چیست؟

اگر یک زندانی ۵۰ کشو را با هم به صورت تصادفی انتخاب کند، به احتمال ۵۰٪ عددش در ۵۰ کشویی است که انتخاب کرده و در نتیجه احتمال اینکه همه نجات یابند برابر است با

$(\frac{1}{2}{)}^{100}\approx 7.8\times 10^{-31}=0.00000000000000000000000000000078$

؛ که عددی بسیار کوچک و تقریباً نزدیک به صفر است. به نظر می‌رسد که وضعیت کاملاً ناامیدکننده است.

استراتژی اصلی

در این استراتژی ما ۵۰ کشو را با هم انتخاب نمی‌کنیم و از اطلاعاتی که با باز کردن کشو به دست می‌آوریم استفاده می‌کنیم. اول کشوها را به ترتیب ۱ تا ۱۰۰ شماره‌گذاری می‌کنیم.الگو:سخ زندانی شمارهٔ n اُم، ابتدا کشوی شمارهٔ n اُم را باز می‌کند اگر عدد درون آن n بود، پس او نجات یافته‌است؛ اگر نه، پس از آن کشویی که شمارۀ آن برابر با شمارۀ درون کشو است را باز می‌کنیم.الگو:سخ این عملیات را تا زمانی که ۵۰ کشو را انتخاب کرده باشیم ادامه می‌دهیم؛ اگر در حین عملیات به n برسد زندانی نجات می‌یابد.

مثال

فرض کنید اعداد درون کشوها این‌گونه باشند:

شمارهٔ کشو	۱	۲	۳	۴	۵	۶	۷	۸
شمارهٔ زندانی	۷	۴	۶	۸	۱	۳	۵	۲

در استراتژی ما، هر زندانی این کارها را انجام می‌دهد:

• زندانی شمارۀ ۱ کشوی شمارۀ ۱ را باز می‌کند و در آن عدد ۷ را می‌بیند. سپس کشوی شمارۀ ۷ را باز می‌کند و در آن عدد ۵ را می‌بیند. بعد کشوی شمارۀ ۵ را باز می‌کند و در آن شمارۀ خود را می‌بیند و نجات می‌یابد.
• زندانی شمارۀ ۲ کشوی شمارۀ ۲، ۴ و سپس ۸ را باز می‌کند و در کشوی شمارۀ ۸، شمارۀ خود را می‌بیند و نجات می‌یابد.
• زندانی شمارۀ ۳ کشوی شمارۀ ۳ و ۶ را باز می‌کند و در کشوی شمارۀ ۶، شمارۀ خود را می‌بیند و نجات می‌یابد.
• زندانی شمارۀ ۴ کشوی شمارۀ ۴، ۸ و سپس ۲ را باز می‌کند و در کشوی شمارۀ ۲، شمارۀ خود را می‌بیند و نجات می‌یابد.
• همین گونه زندانی‌های ۵ تا ۸ نیز شمارۀ خود را پیدا می‌کنند.

در مثال بالا، همه شمارۀ خود را پیدا کردند؛ اما همیشه اینطور نیست. مثلاً فرض کنید اعداد درون کشو ها این‌گونه باشد:

شمارهٔ کشو	۱	۲	۳	۴	۵	۶	۷	۸
شمارهٔ زندانی	۳	۱	۷	۵	۸	۶	۴	۲

در این مثال، زندانی اول کشوهای ۱، ۳، ۷ و ۴ را باز می‌کند؛ اما شمارۀ خود را در آن پیدا نمی‌کند. ولی زندانی شمارۀ ۶، شمارۀ خود را در اولین کشویی که باز می‌کند، می‌یابد.

احتمال نجات یافتن همه

توزیع احتمالاتی بزرگترین دور یک جایگشت رندوم که قسمت سبز نشان دهندهٔ احتمال نجات یافتن همه است

اعداد درون این کشو ها در واقع جایگشتی از اعداد ۱ تا ۱۰۰ است. در نتیجه عدد اولی که زندانی i انتخاب می‌کند، راس متصل به i در گراف جایگشت آن جایگشت است. پس اگر دوری که راس i اُم در آن است کوچکتر از ۵۰ باشد، زندانی نجات می‌یابد.الگو:سخ در نتیجه اگر تمام دور‌های گراف طولشان کمتر از ۵۰ باشد، همه نجات می‌یابند؛ یا به عبارت دیگر اگر طول ماکسیمم دور گراف کمتر مساویِ ۵۰ باشد همه نجات می‌یابند.

اگر $l>50$ باشد، تعداد گراف‌هایی که طول بزرگ‌ترین دور آن ۵۰ است برابر است با:

$(\genfrac{}{}{0ex}{}{100}{l})\cdot (l-1)!\cdot (100-l)!=\frac{100!}{l}.$

اثبات

سری هارمونیک با مساحت زیر هذلولی نشان داده شده تقریب زده می‌شود که خود با لگاریتم تقریب زده می‌شود

اگر $l>50$ باشد و $l$ راس از رئوس گراف را انتخاب کنیم، طول بزرگترین دور گراف برابر $l$ خواهد بود، چون تعداد بقیۀ رأس‌ها از ۵۰ کمتر است حال $l$ تا از رأس‌ها را انتخاب می‌کنیم، $(l-1)!$ تا از گراف‌ها از $l$ راسی که انتخاب کردیم تشکیل یک دور می‌دهند. $(100-l)$ راس باقی‌مانده هم تشکیل یک گراف می‌دهند؛ پس $(100-l)!$ حالت برای بقیۀ رأس‌ها موجود است. احتمال اینکه ماکسیمم دور بزرگتر از ۵۰ باشد برابر است با

$\frac{1}{100!}(\frac{100!}{51}+\dots +\frac{100!}{100})$ در نتیجه احتمال اینکه ماکسیمم دور کمتر مساویِ ۱۰۰ باشد برابر است با

$1-\frac{1}{100!}(\frac{100!}{51}+\dots +\frac{100!}{100})=1-(\frac{1}{51}+\dots +\frac{1}{100})=1-(H_{100}-H_{50})\approx 0.31183,$

که در آن $H_n$ عدد n اُم سری هارمونیک است. پس می بینیم به طرز شگفت‌آوری در ۳۱٪ مواقع همۀ زندانی‌ها با این استراتژی نجات می‌یابند.

احتمال نجات یافتن همه در حالت کلی

حالا اگر به جای ۱۰۰ عدد دلخواه 2n را بگذاریم احتمال نجات یافتن همه با استراتژی اصلی برابر است با:

$1-(H_{2n}-H_n)=1-(H_{2n}-\ln 2n)+(H_n-\ln n)-\ln 2.$

با استفاده از ثابت اویلر-ماسکرونی $\gamma$ در $n\to \mathrm{\infty }$ معادله به این صورت ساده می‌شود:

$\underset{n\to \mathrm{\infty }}{\lim }(H_n-\ln n)=\gamma$

پس از آنجایی که معادله نزولی است به ازای هر n بیش از ۳۰٪ احتمال دارد که همه نجات یابند.

بهینگی

ما بهینگی روش گفته شده را برای سادگی برای $n=10$. ثابت می‌کنیم و به ازای n های دیگر اثبات مشابه دارد.الگو:سخ اول یک بازی جدید به نام بازی ۲ را این‌گونه تعریف می‌کنیم: نفر اول می‌آید و آنقدر کشو باز می‌کند تا به شماره ی ۱ برسد. سپس فردی که کوچک‌ترین شماره‌ای که نفر اول برنداشته را دارد، می‌آید و همین کار را انجام می‌دهد و این روند ادامه پیدا می‌کند. حالا اگر یک نفر بیش از ۵ کشو باز کند بازی را باخته‌ایم.الگو:سخ حالا وقتی تمام ۱۰ کشو باز شد، ۱۰ عدد انتخاب شده تشکیل یک جایگشت از اعداد ۱ تا ۱۰ می‌دهند؛ مثلاً ۲٬۶٬۱٬۴٬۹٬۷٬۱۰٬۸٬۳٬۵. حالا احتمال اینکه نفر اول کشوی شامل ۲ را انتخاب کند برابر است با $\frac{1}{10}$ و همین‌طور احتمال اینکه بعد آن ۱۰ را انتخاب کند برابر است با $\frac{1}{9}$. در نتیجه احتمال اینکه هر جایگشت دلخواه انتخاب شود، برابر $\frac{1}{10!}$ است. در نتیجه پیروزی در بازی دوم مستقل از استراتژی است.الگو:سخ حال همۀ اعدادی که یک نفر انتخاب کرده را در یک دسته قرار می‌دهیم. برای مثال ارائه شده در بالا این‌گونه می‌شود: (۵)(۴٬۹٬۷٬۱۰٬۸٬۳)(۲٬۶٬۱). حال اثبات می‌کنیم هر دسته‌بندی به این شکل را می‌توان با دور های یک گراف جایگشت، تناظر یک به یک داد. اثبات: دور های یک گراف جایگشت را در نظر بگیرید، اعداد هر دور را طوری بچرخانید که عدد مینیمم آخر قرار بگیرد و دورها را به ترتیب مینیمم‌هایشان مرتب کنید. این معادل یک دسته‌بندی از بازی ۲ می‌شودالگو:سخ مثال: (۲٬۴٬۶)(۱٬۳٬۱۰٬۵)(۹٬۷٬۸) -> (۸٬۹٬۷)(۴٬۶٬۲)(۳٬۱۰٬۵٬۱) = ۷ ۹ ۸ ۲ ۶ ۴ ۱ ۵ ۱۰ ۳الگو:سخ پس نتیجه می‌گیریم احتمال اینکه در بازی دوم پیروز شویم برابر با احتمال این است که گراف دور بزرگتر از ۵ نداشته باشد که احتمال آن در بالا محاسبه شده‌است.الگو:سخ حال یک استراتژی در بازی اول (همان استراتژی اصلی) را در نظر بگیرید. هر کاری که یک زندانی در این استراتژی انجام می‌دهد را می‌تواند در بازی دوم هم انجام دهد و اگر نفر قبل از او یک کشو را باز کرده بود، دیگر لازم نیست او نیز همان کشو را باز کند. در هر استراتژی ای که با آن بازی اول را بتوان برد، بازی دوم را هم می‌توان برد.الگو:سخ در نتیجه احتمال اینکه به ازای هر استراتژی بتوان بازی اول را برد، کمتر از احتمال بردن بازی دوم است (که مستقل از استراتژی است). در نتیجه استراتژی ای که ارائه کردیم بهترین استراتژی است.

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «100 prisoners problem». در دانشنامهٔ ویکی‌پدیای انگلیسی.