المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۸

۱۳۹۳ بادکنک را به ترتیب در یک ردیف قرار داده‌ایم. در هر مرحله می‌توانیم یکی از بادکنک‌ها را بترکانیم. فقط باید این شرط رعایت شود که هر بادکنکی که می‌ترکد تعداد بادکنک‌های سمت چپ و راست آن که ترکیده‌اند حداکثر یکی اختلاف داشته باشد. به چند طریق می‌توانیم این بادکنک‌ها را بترکانیم؟

  1. ۲۶۹۶
  2. ۲۶۹۷
  3. ۳۶۹۶
  4. ۳۶۹۷
  5. ۲۱۳۹۳

پاسخ

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

فرض کنید بادکنک ابتدا و انتها در دو حرکت اول نترکند، پس حداقل در حرکت سوم ترکیده‌اند و با توجه به این که حداقل یک طرف آن‌ها دو بادکنک ترکیده و طرف دیگر آنها هیچ بادکنکی نترکیده است به تناقض می‌رسیم. پس دو حرکت اول باید دو بادکنک ابتدا و انتها باشند. به همین ترتیب باقی بادکنک‌ها نیز باید بترکند.


ابزار صفحه