معما

وال المپیاد روسیه 

یک قاضی قصد دارد حکم اعدام را در مورد m زندانی محکوم به مرگ به طریق زیر ( که در این صورت احتمالا بعضی از انها اعدام نمیشوند) اجرا کند

ابتدا انهارا در یک صف مرتب می کند و بعد روی سر هر فرد کلاهی به رنگ سفید یا سیاه قرار می دهد هر فرد فقط رنگ کلاه همه افراد جلویی خود را میبیند بعد زندانی ها ( به ترتیبی که خودشان ان را مشخص میکنند ) رنگ کلاه خود را حدس میزنند هر کسی که اشتباه کند اعدام میشود

زندانی ها حق دارند روز قبل از اجرای حکم با هم مشورت کنند تا تعداد افراد اعدامی که به حداقل برسانند زندانی ها با چه روشی در مورد زنده ماندن حداکثر چند نفر می توانند مطمئن باشند

فرض کنید قاضی به جای دو رنگ از سه رنگ برای کلاه ها استفاده کند در این صورت زندانی ها می توانند زنده ماندن حداکثر چند نفر را می توانند تضمین کنند.