زابونیان در دریای مدیترانه (۲۰ نمره)
کاروان $1398$ نفره زابونیان در حال عبور از دریای مدیترانه بودند که در جزیره آدم خوار ها گیر افتادند. رئیس قبیله آدم خوار ها روش عجیبی را برای محاکمه این $1398$ نفر طراحی کرد. او به هر یک از $1398$ نفر گفت از بین بقیه نام دو نفر متمایز را به او تحویل دهند.
بهیک نفر از کاروان، سربهزیر میگوییم اگر نامش دقیقا یکبار روی کاغذ ها نوشته شده باشد. به فردی از کاروان که نامش بیش از یک بار روی کاغذ ها نوشته شده باشد، رسوا میگوییم. بهیک نفر از کاروان رسواگر میگوییم اگر نام حداقل یک فرد رسوا را روی کاغذش نوشته باشد.
رئیس قبیله، تمام افراد سربهزیر و رسواگر را برای تهیه شام قبیله خواهد کشت و بقیه را آزاد خواهد کرد. حداکثر چند نفر از کاروان زابونیان جان سالم به در خواهند برد ؟
پاسخ
پاسخ برابر $\frac{1398}{3}=466$ است.
ابتدا ثابت میکنیم امکان ندارد بیش از ۴۶۶ نفر زنده بمانند. فرض کنید فرد A زنده بماند و نام افراد B و C را روی کاغذش نوشته باشد. A رسواگر نیست پس B و C را تنها A نوشته است. پس B و C سربه زیر هستند و کشته میشوند. پس به ازای هر زنده، دو مرده وجود دارد. بنابراین حداکثر ۴۶۶ نفر زنده میمانند.
اکنون حالتی ارائه میدهیم که در آن ۴۶۶ نفر زنده بمانند. افراد را به دستههای ۶ تایی تقسیم کرده و نوشته هایشان را به این صورت تعیین میکنیم:
- ۱ نام ۳ و ۴ را بنویسد.
- ۲ نام ۵ و ۶ را بنویسد.
- ۳ تا ۶ هرکدام نام ۱ و ۲ را بنویسند.
در این روش افراد ۱ و ۲ زنده میمانند. پس از هر ۶ نفر ۲ نفر زنده میمانند. ( در کل $\frac{1398}{6}*2=466$ نفر )