المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۴

«ون»، یک خودرو به شکل زیر با یک صندلی راننده و ۱۰ صندلی مسافر است که دو در دارد:

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

  1. ۵۶۰۰
  2. ۵۶۰
  3. ۲۸۰۰
  4. ۳۶۰۰
  5. ۵۱۴۰

پاسخ

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

فردِ روی صندلی ۱ مستقل از بقیه به ۱۰ حالت انتخاب می‌شود. در میان بقیه‌ی افراد، فردی که زودتر از همه پیاده می‌شود، باید روی صندلی شماره ۴ بنشیند. به $\binom{8}{2}$ حالت برای صندلی‌های ۲ و ۳، دو نفر از هشت نفر باقی‌مانده را انتخاب می‌کنیم و به طور یک‌تا در این دو صندلی می‌نشانیم (آن که زودتر پیاده می‌شود، روی صندلی سه می‌نشیند). در میان افراد باقی‌مانده، فردی که زودتر از همه پیاده می‌شود، باید روی صندلی ۷ بنشیند. مانند استدلال قبل $\binom{5}{2}$ حالت برای صندلی‌های ۵ و ۶ داریم و سه نفر باقی‌مانده به طور یک‌تا روی صندلی‌های ۸ و ۹ و ۱۰ می‌نشینند. پس تعداد روش‌ها برابر $$10 \times \binom{8}{2} \times \binom{5}{2} = 2800$$ است.


ابزار صفحه