المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۳

شکل سمت راست را در نظر بگیرید:

سلطان از نقطه‌ی $A$ شروع به کشیدن یک خط شکسته می‌کند. او در هر مرحله نقطه‌ی کنونی را در نظر گرفته و با کشیدن یک پاره‌خط، به یکی از نقاط بالا، بالا-راست یا بالا-چپ (در صورت وجود)‌ می‌رود. پس از چهار مرحله، او به یکی از نقاط بالایی شکل می‌رسد. برای مثال سلطان می‌تواند مسیرش را مانند شکل سمت چپ بکشد. سپس ایلیچ مسیری دیگر با شروع از نقطه‌ی $B$ رسم می‌کند. به چند طریق این کار ممکن است، طوری که دو مسیر کشیده شده در هیچ جایی (چه روی نقاط شکل و چه جای دیگر) یک‌دیگر را قطع نکنند؟

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

پاسخ

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

دو مسیر را با هم جلو می‌بریم. برای بالا بردن دو مسیر در یک مرحله، در هر صورت سه حالت داریم (بررسی حالات به خواننده واگذار می‌شود). با توجه به این که تعداد مراحل چهار تاست، پس در کل $3^4=81$ حالت داریم.


ابزار صفحه