هوپا، انجمن علم ایران

معمای زندانی ها و چراغ

انیشتین گفته هر کی این معما رو حل کنه من خودم اون دنیا شفاعتش میکنم:

فرض کنین توی زندان صد تا زندانی داریم که به زندان های طولانی محکوم شده اند.
این زندانی ها توی سلول های انفرادی نگهداری میشن و هیچ امکان برقراری ارتباط با همدیگر رو ندارند.
یه اتاق بازجویی توی این زندان هست که هیچی توش نیست الا یه لامپ و یه کلید برای روشن و خاموش کردن لامپ.
در ابتدا این لامپ خاموشه.
زندانی ها از سلول خودشون نمیتونن این لامپ رو ببینن.
زندان بان هر روز یکی از زندانی ها رو به صورت تصادفی (با احتمال یکسان برای همه) انتخاب میکنه و میاره به اتاق
این زندانی میتونه کلید چراغ رو تغییر بده (اگه روشنه خاموش کنه یا اگه خاموشه روشن کنه) یا اینکه اون رو دست نزنه و همونطور که هست نگه داره.
مضافا این زندانی میتونه ادعا کنه که تمام صد زندانی حداقل یک بار به این اتاق آورده شده اند.
اگر این ادعا درست باشه هر صد تا زندانی با هم آزاد میشن.
اگر ادعاش غلط باشه هر صد تا با هم اعدام میشن.
زندانی ها اجازه دارند یک شب با هم تو حیاط زندان ملاقات کنند و بر سر یک نقشه برای حل این مساله توافق کنند. از فردای این شب، بازی آغاز خواهد شد و زندانی ها بعد از این همدیگر را نخواهند دید مگر موقع آزادی یا اعدام!

حالا پیدا کنید این زندانی ها چه کار باید کنند؟
*
*
*
ترجيح مي دهم به خاطر آنچه هستم از من متنفر باشند تا به خاطر آنچه نيستم دوستم داشته باشند.

این مال انیشتین بوده؟؟؟
من پارسال این معما رو شنیده بودم ، و کلی هم روش فکر کردم ، ولی خداییش معمای بسیار سختیه ، عمرا کسی که جوابشو ندیده باشه ، بتونه درست جواب بده ، واقعا سخته.
من نتونستم حلش کنم ، لطفا جوابشو بعد از چند روز بزارین ، چون واقعا دیگه از فکر کردن روش خسته شدم.

الان چراغ خاموشه اولین نفر چراغ رو روشن میکنه و بعد نفر بعدی خاموش میکنه اگه یک نفر به طور اتفاقی برای بار دوم وارد اتاق بشه نباید به کلید چراغ دست بزنه و فقط افرادی که برای اولین بار وارد اتاق میشن میتونن حالت کلید رو عوض کنن به این ترتیب آخرین نفر میتونه ادعا کنه که هر صد نفر حد اقل یک بار وارد اتاق شدن

سوال که اینطوری سرکاری میشه ... هر احتمالی رو میشه داد خب که در صورت سوال مطرح نشده...

بعد یه سوال، خود اینیشتین گفته هر کی اینو ج بده شفاعتش میکنه ،اونم تو اون دنیا؟؟؟!!

جوابش اینه:
زندانی ها در شب ملاقات یک ریش سفید برای خود انتخاب میکنند. بقیه زندانی ها باید بر اساس این قرارداد رفتار کنند: هر فرد لامپ را فقط یک بار روشن میکند، یعنی اولین باری که لامپ را خاموش می یابد، آن را روشن می کند. در مابقی دفعات به لامپ دست نمیزند.

رفتار ریش سفید با بقیه فرق میکند. اگر ریش سفید چراغ را روشن بیابد باید آن را خاموش کند و همچنین تعداد دفعاتی را بشمارد که موقع ورود به اتاق با لامپ روشن مواجه شده. حالا اگه عدد شمرده شده به 99 برسه، میتونه ادعا کنه که همه زندانی ها حداقل یک بار به اتاق اومده اند.

سوال یه ذره پیچیده است همین روز ملاقات بگن همه یک بار برن

همه ی باهوشا زندان بان هرروز یک نفرو میبره زندانیا بعد از دیدن هم در صدمین روز میگن همه وارد اتاق شدن به لامپ ربطی نداره

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

آقا من بالاخره بعد از دو ساعت فکر کردن حلّش کردم! فقط راه حلّش ممکنه به درازا بکشه یعنی ممکنه زندانیا توی زندان عمرشون تموم بشه و آزاد نشن ولی حداقل اعدام نمیشن و البته ممکن هم هست که تنها بعد از صد روز از زندان آزاد بشن. البته فرض من اینه که احتمال داره که یه زندانی توی m بار انتخابِ متوالی، تا m بار انتخاب شه و دیگران اصلاً انتخاب نشن!

زندانیا باید هر روز رو توی دیوار سلّولشون علامت بذارن و هر وقت که انتخاب شدن متوجه باشن که چندمین زندانی هستن. زندانی هایی که مضرب دُرُستی از 100 هستن و به اتاق لامپ برده میشن، زندانی های مهمی هستن و باید خیلی دقت کنن.

هر زندانی (بجز زندانی های مضارب صد) موظفه که به لامپ خاموش اصلاً دست نزنه مگر اینکه اون زندانی برای بار دوم انتخاب شده باشه که باید لامپ خاموش رو روشن کنه. زندانی های دیگه (بجز زندانی های مضارب صد) اگه با لامپ روشن مواجه شدن اصلاً نباید کاریش داشته باشن حالا چه برای اولین بار باهاش مواجه بشن یا چندمین بار. با این توضیحات دور اول (صد روز اول) شروع میشه و زندانیا هر روز به اتاقِ لامپ برده میشن. حالا:

1- اگه زندانی صدم (بعد از صد روز) به لامپ خاموش برخورد بکنه و متوجه باشه که توی این صد روز خودشم اصلاً انتخاب نشده، کار تمومه و روز صدم اعلام می کنه که هر زندانی فقط یه بار به داخل اتاق برده شده و زندانی ها همه آزاد میشن و اون دور به نام ((دور طلایی)) شناخته میشه. ولی اگه در روز صدم همون زندانی صدم متوجه شد که لامپ خاموشه ولی خودش برای بار دوم داره انتخاب میشه بدون اینکه به لامپ دست بزنه و به همون صورت خاموش لامپ رو رها می کنه. حالا روز بعد که زندانی 101 متوجه می شه که کسی هنوز آزاد نشده و لامپ خاموش به اون رسیده متوجه می شه که به دلایلی زندانیِ کلیدیه صدم نتونسته اعلام آزادی کنه و زندانی 101 باید بازی رو از اول شروع کنه. وقتی بازی به صد دوره دوم کشیده شد، تمام زندانیا باید تعداد دفعاتی رو که تکراری انتخاب شدن رو فراموش کنن و بازی رو راستو حُسینی از اول شروع کنن! در این حالت زندانی دویستم کسیه که کار زندانی صدم رو باید تکرار کنه.

2- اما اگه زندانی صدم به لامپ روشن رسید، متوجه میشه که حداقل یه نفر به صورت تکراری انتخاب شده. حالا این زندانی بدون توجه به این نکته که خودش در انتخاب صدم تکراری هست یا نه باید لامپ رو خاموش کنه و حرفی نزنه. در این حالت باز وقتی نوبت زندانی 101 می رسه متوجه می شه که تکراری صورت گرفته و بازی باید از اول تکرار بشه.

دقت کنید که هیچ زندانی اجازه ی اظهار نظر نداره مگر زندانیایی که مضرب صحیحی از صد هستن. این روند باید اونقدر تکرار بشه تا زندانی 100n متوجه بشه که لامپ خاموش بهش رسیده و خودش هم توی دورِ n اُم برای اولین بار انتخاب شده و فریاد رهایی رو سر بده! یعنی با این کار، آخرین زندانیِ دورِ n اُم (یعنی زندانی شماره ی 100n) می تونه با اطمینان بگه که دورِ مذکور تنها دوریه که همه ی زندانیا فقط برای یه بار توش انتخاب شدن پس همشون مطمئناً حداقل یه بار انتخاب شدن. اما عددِ n می تونه از یک تا اعداد خیلی بزرگ (بینهایت) متغیر باشه و زندانیا باید شانس بیارن که ((دوره طلایی)) توی n های کوچیک نصیبشون بشه!

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

برای حل این مساله، زندانی ها باید یک راه حل ساده و قابل تکرار برای تعیین اینکه کدام یک از آن‌ها به اتاق بازجویی آورده شده است، ارائه دهند. یک راه حل ممکن برای این مساله، استفاده از یک سیستم شمارش دودی است.

زندانی ها می‌توانند به این صورت این سیستم را پیاده‌سازی کنند:

1. هر زندانی یک عدد دودی (binary) در نظر می‌گیرد که با توجه به شماره سلولش تعیین می‌شود به عنوان مثال اگر شماره سلول یک زندانی ۱ باشد، او یک عدد دودی ۰۰۰۰۰۰۱ می‌گیرد.

2. هر زندانی در هنگامی که به اتاق بازجویی آورده می‌شود، کلید چراغ را به صورت تصادفی فشار می‌دهد، با این شرط که اگر عدد دودی او در مبنای دو، از راست به چپ، با همه‌ی عدد دودی‌هایی که تاکنون در اتاق بازجویی آمده‌اند، متفاوت بود، کلید را خاموش می‌کند. در غیر این صورت، کلید را روشن می‌گذارد.

3. پس از اینکه همه‌ی زندانی‌ها به اتاق بازجویی آمده‌اند، اگر لامپ روشن باشد، زندانی که آخرین بار کلید چراغ را فشار داده است، به عنوان زندانیی که به اتاق بازجویی آورده شده است، شناسایی می‌شود. اگر لامپ خاموش باشد، هیچ کدام از زندانی‌ها به عنوان زندانیی که به اتاق بازجویی آورده شده است، شناسایی نمی‌شوند.

این راه‌حل قابل تکرار است زیرا زندانی‌ها می‌توانند از این سیستم برای تمام دفعاتی که به اتاق بازجویی آورده می‌شوند، استفاده کنند. همچنین، با توجه به اینکه هیچ کدام از زندانی‌ها نمی‌توانند با یکدیگر در ارتباط باشند، هیچ کدام نمی‌توانند این سیستم را تغییر دهند و احتمال اینکه یک زندانی ادعا کند که تمام زندانی‌ها به اتاق بازجویی آورده شده‌اند، به صفر میل می‌کند. با این روش، همه‌ی زندانی‌ها با همکاری تمامی زندانی‌ها در یک شب ملاقات، می‌توانند به طور هوشمندانه و با استفاده از منطق و حدس و گمان، به این سیستم دودی مبتنی بر شمارش، دسترسی پیدا کنند و با موفقیت پاسخ به این مسأله را به دست آورند
، بنابرین زندانی‌ها با استفاده از سیستم دودی مبتنی بر شمارش، می‌توانند به این مسأله پاسخ دهند و ادعای آن‌ها را تأیید یا رد کنند و اگر ادعای آن‌ها تأیید شود، همه‌ی زندانی‌ها آزاد می‌شوند.