المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۴

مورچه‌ای می‌خواهد در مکعّب روبه‌رو از رأس $A$، با حرکت روی پاره‌خط‌ها، به رأس $B$ (رأس مقابل $A$) برود. فرض کنید در هر حرکت مورچه از یک سر پاره‌خط به سر دیگر آن می‌رود. می‌دانیم بعد از ۵ حرکت مورچه روی رأس $B$ قرار دارد. او به چند طریق می‌تواند این مسیر را طی کرده باشد؟

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

پاسخ

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

می‌دانیم که برای رسیدن از $A$ به $B$ دقیقا باید یک عمل بالا، یک راست و یک عقب انجام شود. در نتیجه باید جایگشتی از $RUB$ را داشته باشیم. برای اینکه در حرکت پنجم در نقطه $B$ باشیم باید دقیقا یک حرکت به صورت رفت و برگشت اضافه انجام شود. حالت اول فرض می‌کنیم دو حرکت اضافه شده حرکت به راست و چپ است. در نتیجه باید جایگشتی از رشته $RRLUB$ به عنوان دنباله حرکات انتخاب شود. پس تعداد روشها برای این حالت !5 است ولی باید این نکته را در نظر داشت که حرکت به سمت راست و چپ قابلیت جابجایی ندارند. یعنی نمی‌توانیم ابتدا به سمت چپ حرکت کرده و سپس دو بار به سمت راست حرکت کنیم زیرا از مکعب خارج خواهیم شد. برای حل این مشکل فرض کنیم سه حرف $RRL$ با یکدیگر فرقی ندارند و در عوض باید به ترتیب $RLR$ در دنباله بیایند. در نتیجه برای حالت اول به اندازه $\frac{5!}{3!}$ روش وجود دارد. حالت دوم به صورتی است که به جای اضافه شدن دو حرکت راست و چپ اضافه دو حرکت بالا و پایین اضافه داشته باشیم یعنی رشته به صورت $RUDUB$ در بیاید. و برای حالت سوم نیز رشته باید به صورت $RUBFB$ باشد. دو حالت فوق همانند حالت اول محاسبه خواهند شد و در کل $20×3=60$ روش داریم که همان گزینه ج است.


ابزار صفحه