سوال ۱۲
شکل مقابل چند جزیره را نشان می دهد که با تعدادی پل به هم متصل شده اند. حمید و رشید در ساعت ۱۲ ظهر در جزیره‌ي $A$ هستند. آن‌ّها باید به کشتی‌ای که در ساحل جزیره‌ي $B$ لنگر انداخته و در ساعت ۴ بعد از ظهر حرکت می کند برسند. حرکت از ابتدای یک پل به انتهای آن یک ساعت زمان می برد و یک پل در هر لحظه می تواند وزن یک نفر را تحمل کند و اگر در یک لحظه هم حمید و هم رشید روی آن باشند، پل فرو می ریزد. چند حالت مختلف برای مسیر حرکت این دو وجود دارد به طوری که هر دوی آن ها به کشتی جزیره ی $B$ برسند؟
- ۱۲
- ۲۰
- ۱۶
- ۳۶
- ۲۸
راهنمایی
دقت کنید که طول کوتاه‌ترین مسیری که از $A$ به $B$ می‌رسد، چهار است.
راهنمایی
پس هر دو در هر ساعت می‌بایست به تعبیر شکل، یک واحد به پایین حرکت کنند.
راهنمایی
در ساعت اول یک نفر می‌بایست به سمت راست برود و دیگری به سمت چپ.
راهنمایی
بر روی تعداد افرادی که پس از ساعت دوم بر دایره‌ی میانی تصویر قرار دارند حالت بندی کنید.
پاسخ
گزینه‌ی ۲ درست است.
در ساعت اول دو حالت برای حرکت آن‌ها وجود دارد. در ساعت دوم اگر هر دو به جزیره‌ی وسط نقشه نروند، بقیه مسیر به صورت یکتا مشخص می‌شود. تعداد این حالات برابر ۸ است. اگر هر دو به جزیره‌ی وسط سفر کنند دو حالت برای ادامه‌ی حرکت وجود دارد. در نتیجه جواب نهایی برابر است با:
$$2×(8+2)=20$$
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
