من پت هستم

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

حل این مساله در حقیقت به کمک استقرا امکان پذیر است. در استقرا اگر بتوانیم مساله را برای یک عدد مثلا k=1 و یا k=2 (پایه‎ی استقرا) حل کنیم، و پس از آن با فرض دانستن جواب مساله برای k (فرض استقرا) بتوانیم جواب مساله برای k+1 (حکم استقرا) هم پیدا کنیم، در حقیقت مساله را برای همه‌ی حالت‌های ممکن ( البته ممکن و بزرگتر از پایه‌ی استقرا) حل کرده‌ایم. حالا برگردیم سر مساله‌ی خودمان و راه حلش.

حالا فرض کنبد اگر k نفر با کلاه سفید در جلسه وجود داشته باشند، افراد حاضر در جلسه بین k-1امین و kامین باری که پادشاه دست می‌زند متوجه رنگ کلاه خود خواهند شد (قبلا نشان داده‌ایم که این فرض برای k=1 و k=2 درست است). حالا با در نظر گرفتن این فرض بیایید حالتی را بررسی کنیم که k+1 نفر با کلاه سفید در جلسه حاضرند.

حالا برای سادگی فرض کنید که شما یک کلاه سفید هستید. در این حالت شما k کلاه سفید در جلسه می‌بینید (هنوز هم از رنگ کلاه خودتان بی‌خبرید) ، بنابراین با توجه به فرض پاراگراف بالا، انتظار دارید اگر کلاه‌تان سیاه باشد، کلاه سفیدها بتوانند رنگ کلاهشان را پس از k-1امین باری که پادشاه دست می‌زند تشخیص بدهند، ولی خوب همچین اتفاقی نمی‌افتد، بنابراین شما و تمام کلاه سفیدها پس از k-1امین دست پادشاه متوجه سفید بودن رنگ کلاه‌تان خواهید شد و پس از کلاه سفیدها، کلاه سیاه‌ها هم متوجه رنگ کلاه‌شان خواهند شد.

اگر فکر می‌کنید استدلال بالا بیش از حد پیچیده است و قرار نیست که به درستی کار کند بیایید با یک مثال آن را واضح‌تر کنیم. فرض کنید k=3 است. اگر شما کلاهتان سفید باشد، ۲ نفر را با کلاه سفید می‌بینید، پس انتظار دارید که اگر فقط این ۲ نفر با کلاه سفید باشند، پس از بار اولی که پادشاه دست می‌زند باید بتوانند رنگ کلاهشان را تشخیص بدهند، ولی هنگامی که پادشاه برای بار دوم هم دست می‌زند و شما می‌فهمید که کلاه خودتان هم سفید بوده‌است. به همین ترتیب برای k=4 و k=5 و … هم می‌توان این استدلال را ادامه داد.

مطلب دیگری که توجه به آن می‌تواند جالب باشد، مساله‌ی آن یک بیتی است که در قسمت دوم به آن اشاره کردیم. هر فرد نیاز به یک بیت اطلاعات دارد که بتواند جانش را نجات بدهد. امکان دارد که این سوال پیش بیاید که افراد از کجا  این یک بیت دانش  را بدست می‌آورند. از آنجایی که اگر فردی در جلسه باشد و k کلاه سفید ببیند، می‌داند که پادشاه حداقل k-1 بار دست خواهد زد، پس شنیدن این دست‌ها برایش اطلاعاتی در بر ندارد، ولی پس از بار k-1 ام، دو حالت امکان وقوع دارد، یکی دیدن شادی کلاه سفیدها و یا شنیدن صدای یک دست زدن دیگر که رفع این ابهام (دیدن شادی و یا صدای دست) می‌تواند یک بیت ازطلاعاتی را به هر فرد بدهد که جانش فرد در گرو آن است. و اما آخرین نکته گفته بودم که برای توصیف شرایط (رنگ کلاه‌ها) در حدود N بیت اطلاعات نیاز داریم و سوال این است که چرا حدود N بیت و نه دقیقا N بیت؟ N بیت می‌تواند ۲ به توان N حالت را توصیف کند ولی در این بازی ما یک حالت کم‌تر از این تعداد داریم و برای همین اندکی کمتر از N بیت اطلاعات نیاز داریم.