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