المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۴:سوالات ۲۷ و ۲۸

سوالات ۲۷ و ۲۸

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

با توجه به توضیحات بالا به ۲ سؤال زیر پاسخ دهید.

سوال ۲۷

اگر کشور پنیر شمالی ۱۰۰ نیرو و کشور پنیر ‌جنوبی ۴۵ نیرو در اختیار داشته‌ باشد. کشور پنیر شمالی حداکثر چند جزیره را می‌تواند تصاحب کند؟

  1. ۷
  2. ۳
  3. ۴
  4. ۵
  5. ۶

پاسخ

گزینه‌ی ۵ درست است.

چون کشور پنیر ‌جنوبی از نحوه‌ی چینش کشور پنیر ‌شمالی اطلاع می‌یابد یک استراتژی بهینه برای آن این است که همیشه سعی کند جزیره‌هایی که کمترین نیرو را دارند اشغال کند. اما می‌دانیم مجموع تعداد نیروهایی که پنیر ‌شمالی به چهار جزیره‌ای که کم‌ترین نیروها را دارند اعزام کرده است حداکثر ۴۰ است (چرا؟). در نتیجه کشور پنیر ‌جنوبی می‌تواند حداقل ۴ جزیره را تصاحب کند. اما اگر کشور پنیر ‌شمالی به هر جزیره دقیقا ۱۰ نیرو اعزام کند پنیر ‌جنوبی نمی‌تواند بیش‌تر از ۴ جزیره‌ را تصاحب کند و در نتیجه پنیر ‌شمالی می‌تواند ۶ جزیره را تصاحب کند.

سوال ۲۸

اگر کشور پنیر ‌جنوبی ۴۵ نیرو در اختیار داشته باشد، کشور پنیر ‌شمالی حداقل چند نیرو باید داشته باشد تا مطمئن باشد که نیمی از جزیره‌ها را تصاحب می‌کند؟

  1. ۶۸
  2. ۶۹
  3. ۷۰
  4. ۷۳
  5. ۷۵

پاسخ

گزینه‌ی ۲ درست است.

اگر پنیر ‌شمالی در هر جزیره ۷ نیرو قرار دهد، پنیر ‌جنوبی حداکثر می‌تواند ۵ جزیره را اشغال کند. اما پنیر ‌شمالی می‌تواند در یک جزیره ۶ نیرو قرار دهد به طوری که باز هم پنیر ‌جنوبی نتواند بیش‌تر از ۵ جزیره را اشغال کند. با استفاده از اصل لانه‌کبوتری می‌توان نشان داد که پنیر ‌شمالی با کمتر از ۶۸ نیرو نمی‌تواند این کار را انجام دهد، چون در این صورت پنیر ‌جنوبی با ۴۵ نیرو می‌تواند حداقل ۶ جزیره‌ را تصاحب کند (چرا؟). البته با ۶۸ نیرو اگر چه پنیر ‌جنوبی نمی‌تواند بیش‌تر از ۵ جزیره را تصاحب کند اما پنیر ‌شمالی هم نمی‌تواند مطمئن باشد که ۵ جزیره را تصاحب می‌کند، زیرا ممکن است در یکی از جزایر تساوی رخ دهد.


ابزار صفحه