المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۲:سوال ۲۳

سوال ۲۳

اگر مسأله‌ی قبل این‌گونه تغییر کند که ظرف‌ها دور یک میز دایره شکل قرار گرفته‌اند و در هر مرحله فقط می‌توانیم به ‎۴‎ ظرف متوالی هر کدام ‎۱‎ گردو اضافه کنیم، از وضعیتی که همه‌ی ظرف‌ها خالی هستند به کدام‌یک از وضعیت‌های زیر می‌توان رسید؟‎

  1. ‎$c،b‎،a$‎ و $d$
  2. $c$‎ و ‎$d$
  3. $b$‎ $c$،‎‎ و ‎$d$
  4. $a$‎ و $‎b$
  5. $a$،‎ $c$ و $d$‎

پاسخ

گزینه (؟) درست است.

برای تولید $a$ هر یک از کمان‌های $DE،CD،BC،AB$ و $EA$ سه بار و سپس کمان $AB$ را ۴ بار دیگر و کمان $MN$ را ۱۴ بار انتخاب می‌کنیم.

وضعیت $b$ قابل تولید نیست.

کمان‌هایی که شامل هر دو خانه ۱۲ و ۴ باشند مجموعا حداکثر ۴ بار به کار می‌روند. بنابراین کمان‌هایی که شامل ۱۲ بوده ولی شامل ۴ نباشند حداقل برابر ۸ می‌باشد(چنین کمانی فقط کمانی می‌تواند باشد که هر چهار عدد ۸٬۹٬۱۲ و ۸ را در بر دارد). بنابراین کمان یادشده دقیقا ۸بار و کمان ۹ و ۱۲ و ۴ و ۹ دقیقا ۱ بار به کار می‌رود. اگر گردوهای اضافه شده را کم کنیم به حالت مقابل می‌رسیم که قابل تولید نیست.

برای تولید وضعیت $c$ هر یک از کمان‌های بزرگ $BC،AB$ و $CA$ را ۵۱ بار انتخاب می‌کنیم.

برای تولید وضعیت $d$ کمان سمت راست $AB$ را ۱ بار٬ کمان سمت راست $CD$ را ۲ بار و بالاخره کمان سمت چپ $AB$ را ۴ بار انتخاب می‌کنیم.


ابزار صفحه