سوال ۲۳
شکل سمت راست را در نظر بگیرید:
سلطان از نقطه‌ی $A$ شروع به کشیدن یک خط شکسته می‌کند. او در هر مرحله نقطه‌ی کنونی را در نظر گرفته و با کشیدن یک پاره‌خط، به یکی از نقاط بالا، بالا-راست یا بالا-چپ (در صورت وجود) می‌رود. پس از چهار مرحله، او به یکی از نقاط بالایی شکل می‌رسد. برای مثال سلطان می‌تواند مسیرش را مانند شکل سمت چپ بکشد. سپس
ایلیچ
مسیری دیگر با شروع از نقطه‌ی $B$ رسم می‌کند. به چند طریق این کار ممکن است، طوری که دو مسیر کشیده شده در هیچ جایی (چه روی نقاط شکل و چه جای دیگر) یک‌دیگر را قطع نکنند؟
- ۱۳
- ۹۶
- ۵۵
- ۲۷
- ۸۱
راهنمایی
دقت کنید در یک سطر از نقاط، یکی می‌بایست برای علامت سلطان و دیگری می‌بایست برای علامت ایلیچ در نظر گرفته شود.
راهنمایی
آیا ممکن است در یک سطر، نقطه‌ی ایلیچ قبل از نقطه‌ی سلطان قرار داشته باشد و در سطر دیگر، به ترتیب عکس درآید؟
راهنمایی
در هر سطر سه حالت برای انتخاب جای علامت‌های سلطان و ایلیچ قابل انتخاب است. آیا ممکن است خط‌های رسم شده با شروط راهنمایی‌های پیشین تداخل داشته باشند؟
پاسخ
گزینه‌ی ۵ درست است.
دو مسیر را با هم جلو می‌بریم. برای بالا بردن دو مسیر در یک مرحله، در هر صورت سه حالت داریم (بررسی حالات به خواننده واگذار می‌شود). با توجه به این که تعداد مراحل چهار تاست، پس در کل $3^4=81$ حالت داریم.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
