المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۸

در شکل مقابل مبینا روی نقطه‌ي $A$ ایستاده است. او فقط می تواند به صورت ساعت گرد روی کمان ها حرکت کند.

مبینا به چند طریق می تواند با شروع از نقطه‌ی $A$ و حرکت کردن روی کمان ها خود را به مکان اولیه اش برساند با فرض اینکه از هر نقطه حداکثر سه بار عبور کند؟ مثلا یک مسیر ممکن این است که از کمان های بیرونی سه بار عبور کند و در نقطه‌ي $A$ متوقف شود.

  1. $۲\times ۳^۵ + ۱$
  2. ۱۰۰
  3. ۱۰۱
  4. $۲^۵ + ۳^۵ $
  5. $۳^۶ $

پاسخ

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

بر اساس تعداد دورهایی که در نهایت می‌زنیم تقسیم‌بندی می‌کنیم (تعداد دفعاتی که از $A$ می‌گذریم:

اگر یک دور بزنیم، هر دور کوچک را می‌توانیم صفر، یک یا دو بار طی کنیم. در نتیجه تعداد این حالات برابر $3^5$ است.

اگر دو دور بزنیم، در هر دور کوچک سه حالت ممکن است (یا اصلا دور کوچک را طی نمی‌کنیم، یا فقط در دور اول یا فقط در دور دوم آن را دور می‌زنیم). پس تعداد این حالات نیز $3^5$ است.

در نهایت اگر سه دور بزنیم، دنباله حرکات به صورت یکتا به‌دست می‌آید.

در نتیجه کل حالات برابر است با: $2×3^5+1$.


ابزار صفحه