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