معمای کمی تا نسبتی سخت!

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

سوال:با چه روشی ممکن است که فقط افراد خالدار در پایان مهلت تعیین شده(n روز به ازای n خالدار)از سالن خارج شوند؟

ππ

ππ

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

از طرف دیگر بقیه افراد بدون خال می بینند یک نفر خال دارد ولی خودشان نمی دانند خال دارند یا نه. مثل بالا برای خودشان استدلال می کنند که اگر خودشان خال نداشته باشند آن فرد خالدار باید امروز از سالن خارج شود و اگر خودشان خال داشته باشند آن فرد دیگر امروز را منتظر خواهد ماند. آن فرد خالدار روز اول از سالن خارج می شود و بقیه می فهمند که خودشان خالدار نبودند.

حالا برای دو نفر همین استدلال رو تکرار کنید. فرض کنید دو نفر در سالن خال دارند. فردی که خالدار است می بیند یک نفر در سالن خال دارد ولی نمیداند خودش هم خال دارد یا نه. با خودش می گوید اگر من خال نداشته باشم آن فرد خالدار باید امروز از سالن خارج شود و اگر خال داشته باشم باید منتظر بماند. آن فرد دیگر هم همین جور استدلال میکند و هر دو روز اول را کاری نمی کنند و منتظر می مانند. در نتیجه می فهمند که هر دو تا خالدار هستن و روز دوم از سالن خارج می شوند.

اما آن هایی که خال ندارند می بینند دو نفر در سالن خال دارند. آن ها دو روز صبر میکنند تا سرنوشت این دو نفر معلوم شود و چون روز دوم آن دو نفر از سالن خارج می شوند می فهمند که خودشان خال نداشتند.

به همین ترتیب می توانند برای سه نفر و چهار نفر و … استدلال را تکرار کنیند . در نتیجه اگه n نفر خالدار باشن تا روز n-1 ام صبر میکنند و بقیه که خال ندارند تا روز n ام. روز n ام افراد خالدار دسته جمعی از سالن خارج می شوند و از اینجا بقیه می فهمند که خودشان خال ندارند. یعنی تا صبح روز n+1 فرد خالداری در سالن وجود نخواهد داشت.
منبع:weblog.roshdmag