سوال ۳۴
بین شهرهای $A$ و $B$ یک جاده‌ِی باریک وجود دارد. در این جاده ۱۰ تانکر بنزین، به ترتیب با شماره‌های ۱ تا ۱۰ پشت سر هم و با سرعت‌های متفاوت از $A$ به سمت $B$ در حرکت‌اند. در ابتدا هیچ دوتایی از تانکرها روی یک نقطه از جاده نیستند. راننده‌های این تانکرها خواب هستند و بنابراین از ترمز خبری نیست. اگر دو تانکر به هم برسند، هر دو منفجر و متلاشی می‌شوند به طوری که اثری از آنها باقی نمی‌ماند. به این ترتیب تانکرهای بعدی می‌توانند از محلّ تصادف عبور کنند. اگر بدانیم که هیچ‌وقت بیشتر از دو تانکر در یک لحظه تصادف نمی‌کنند، مجموعه تانکرهایی که به شهر $B$ می‌رسند، چند حالت مختلف می‌تواند داشته باشند؟
- ۵۵
- ۸۹
- ۱۴۴
- ۵۱۲
- ۱۰۲۴
پاسخ
گزینه‌ی (۲) درست است.
$f(n)$: تعداد حالت‌هایی که تانکرها به مقصد می‌رسند اگر در آغاز $n$ تانکر داشته باشیم (و هر تانکر تنها با تانکرهایی تصادف کند که که دارای عددهای متوالی هستند).
روی اولین تانکر حالت‌بندی می کنیم:
1-به مقصد می‌رسد :
در اینصورت تانکر اول با هیچ تانکری برخورد نکرده است پس تعداد حالت‌ها برابر است با .$f(n-1)$
2- به مقصد نمی‌رسد :
در این حالت تانکر اول با تانکر دوم برخورد کرده است. پس $2$ تانکر اول حذف می‌شوند و تعداد حالت‌ها برابر است با $f(n-2)$.
در نتیجه $f(n) = f(n-1) + f(n-2)$. که با توجه به حالت‌های اولیه داریم: $f(10) = 89$
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
