من پت هستم

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

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

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

در صورتی که k=2 باشد: در این حالت افراد کلاه سفید هر کدام یک فرد دیگر را با کلاه سفید می‌بینند. ولی چون رنگ کلاه خودشان را نمی‌دانند منتظر واکنش آن نفر دیگر می‌مانند. در هنگامی که برای اولین بار پادشاه دستانش را برهم می‌زند. هر کدام از کلاه سفیدها چون که واکنشی از جانب یک کلاه سفید دیگر ندیده است می فهمد که حتما آن فرد هم یک کلاه سفید می‌دیده‌ایست، یعنی خودش هم باید کلاه سفید باشد. وقتی که این دو نفر به پادشاه رنگ کلاه‌شان را اعلام می‌کنند کلاه سیاه‌ها هم می‌فهمند که کلاه خودشان سفید نیست و در نتیجه سیاه است.

خوب بررسی سایر موارد k هم که به نظر می‌رسد که زیاد سخت نباشد و از آنجایی که k نمی‌تواند از N بزرگ‌تر باشد، سرانجام پس از تعداد متناهی دست زدن پادشاه، می‌توانیم خاطر جمع باشیم که این نخبگان ما متوجه رنگ کلاهشان خواهند شد.

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