سوال ۱۸
در شکل مقابل مبینا روی نقطه‌ي $A$ ایستاده است. او فقط می تواند به صورت ساعت گرد روی کمان ها حرکت کند.
مبینا به چند طریق می تواند با شروع از نقطه‌ی $A$ و حرکت کردن روی کمان ها خود را به مکان اولیه اش برساند با فرض اینکه از هر نقطه حداکثر سه بار عبور کند؟ مثلا یک مسیر ممکن این است که از کمان های بیرونی سه بار عبور کند و در نقطه‌ي $A$ متوقف شود.
- $۲\times ۳^۵ + ۱$
- ۱۰۰
- ۱۰۱
- $۲^۵ + ۳^۵ $
- $۳^۶ $
راهنمایی
بر تعداد دفعاتی که نقطه‌ی $A$ را می‌بینید حالت بندی کنید.
راهنمایی
در راستای راهنمایی پیشین، اگر بجز زمان شروع فقط یک‌بار نقطه‌ی $A$ را ببینیم، به ازای گذشتن از هر نقطه‌ی تقاطع دو کمان، چند حالت عبور خواهیم داشت؟
راهنمایی
در راستای راهنمایی پیشین، دقت کنید هر بار که به یک تقاطع می‌رسید، می‌توانید انتخاب کنید از کدام یک از خطوط محل تقاطع مسیر را ادامه دهید.
راهنمایی
به شکل مشابه برای زمانی که غیر از لحظه‌ی شروع، دو بار از نقطه‌ی $A$ بگذریم حالت بندی کنید در هر یک از تقاطع‌ها چه اتفاقی رخ دهد.
پاسخ
گزینه‌ی ۱ درست است.
بر اساس تعداد دورهایی که در نهایت می‌زنیم تقسیم‌بندی می‌کنیم (تعداد دفعاتی که از $A$ می‌گذریم:
اگر یک دور بزنیم، هر دور کوچک را می‌توانیم صفر، یک یا دو بار طی کنیم. در نتیجه تعداد این حالات برابر $3^5$ است.
اگر دو دور بزنیم، در هر دور کوچک سه حالت ممکن است (یا اصلا دور کوچک را طی نمی‌کنیم، یا فقط در دور اول یا فقط در دور دوم آن را دور می‌زنیم). پس تعداد این حالات نیز $3^5$ است.
در نهایت اگر سه دور بزنیم، دنباله حرکات به صورت یکتا به‌دست می‌آید.
در نتیجه کل حالات برابر است با: $2×3^5+1$.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
