سوال ۱۸
۱۳۹۳ بادکنک را به ترتیب در یک ردیف قرار داده‌ایم. در هر مرحله می‌توانیم یکی از بادکنک‌ها را بترکانیم. فقط باید این شرط رعایت شود که هر بادکنکی که می‌ترکد تعداد بادکنک‌های سمت چپ و راست آن که ترکیده‌اند حداکثر یکی اختلاف داشته باشد. به چند طریق می‌توانیم این بادکنک‌ها را بترکانیم؟
- ۲۶۹۶
- ۲۶۹۷
- ۳۶۹۶
- ۳۶۹۷
- ۲۱۳۹۳
راهنمایی
دو بادکنک دلخواه را در دو مرحله بترکانید و در هر مرحله، مجموعه‌ی بادکنک‌هایی را که می‌توان ترکاند، مشخص کنید.
راهنمایی
وضعیت بادکنک‌های اول و آخر را در هر مرحله بررسی کنید.
پاسخ
گزینه‌ی ۱ درست است.
فرض کنید بادکنک ابتدا و انتها در دو حرکت اول نترکند، پس حداقل در حرکت سوم ترکیده‌اند و با توجه به این که حداقل یک طرف آنها دو بادکنک ترکیده و طرف دیگر آنها هیچ بادکنکی نترکیده است به تناقض می‌رسیم. پس دو حرکت اول باید دو بادکنک ابتدا و انتها باشند. به همین ترتیب باقی بادکنک‌ها نیز باید بترکند.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
