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