۱۰ ماشین شماره دار در یک مسیر می روند، اگر در صورت تصادف ناپدید شوند و بیشتر از یک تصادف در آن واحد نداشته باشیم، چند حالت برای ماشین های موفق داریم؟

Question

بین شهرهای $A$ و $B$ یک جادهٔ باریک وجود دارد. در این جاده ۱۰ تانکر بنزین به ترتیب با شماره‌های ۱ تا ۱۰ پشت سر هم و با سرعت‌های متفاوت از $A$ به سمت $B$ در حرکت‌اند. در ابتدا هیچ دوتایی از تانکرها روی یک نقطه از جاده نیستند. رانندهٔ این تانکرها خواب هستند و بدین ترتیب از ترمز خبری نیست. اگر دو تانکر به هم برسند، هر دو منفجر و متلاشی می‌شوند به طوری که اثری از آنها باقی نمی‌ماند. به این ترتیب تانکرهای بعدی می‌توانند از محل تصادف عبور کنند. اگر بدانیم که هیچ وقت بیشتر از دو تانکر در یک لحظه تصادف نمی‌کنند، چند حالت برای مجموعهٔ شماره‌های تانکرهایی که به شهر $B$ می‌رسند وجود دارد؟

Comments

@احمدرضا137 پیشنهاد می کنم که متن سوال را یک بار بخوانید و حرف هایی که جا افتاده است را بنویسید.

---

@احمدرضا137 یک امتیاز منفی  $(-1)$ برای اینکه هنوز سوال را ویرایش نکرده اید. به مرجع مراجعه کنید و بر اساس آن سوال را ویرایش کنید.

---

سوال را عینا از روی مرجع نوشتم. مجموع یا مجموعه در معنای اصلی سوال ابهام یا اشکالی ایجاد نمی کند. پس ضرورتی برای ویرایش نیست. تا مرجع مطمئن تری پیدا نکنم نمی توانم سوال را دستکاری کنم.

---

@احمدرضا137 به نظرتان کلمه های شار و نفجر اینجا معنی دارند؟
کلمه مجموع باید به مجموعه تغییر یابد زیرا سوال را بی معنی می کند.
به هر حال بنده پاسخم را بر می دارم تا زمانی که سوال را ویرایش کنید.

Answer 1

به نام خدا.

توجه: اگر دو تانکر به هم نزدیک شوند، آنگاه انفجار رخ‌ می دهد

بیایید مسئله را برای تعداد کمتر بررسی کنیم. اگر تعداد تانکر ها $2$ تا باشد، آنگاه تانکرهایی که به $B$ می رسند، می تواند هیچ کدام یا هر دو باشد. برای سه تانکر نیز سه حالت داریم. برای $4$ تا $5$ حالت داریم. به یک حدس می رسیم:($F_n$ تعداد حالت هایی است که $n$ تانکر می توانند به $B$ بروند.)

$F(n)=F(n-1)+F(n-2)$

از اثبات ترکیبیاتی کمک می گیریم.

تانکر شماره یک را در نظر بگیرید.

حالت اول: این تانکر منفجر نشود. در این صورت باید در مجموعه تانکر هایی که به مقصد می رسند باشد. پس تعداد حالت ها می شود $F(n-1)$.

حالت دوم: این تانکر به مقصد نرسد. یعنی منفجر شود. پس باید تانکر شماره $2$ نیز منفجر شود. زیرا اگر منفجر نشود آنگاه شماره یک هم هیچ وقت منفجر نمی شود. بدون اینکه به پاسخ اشکال وارد شود، فرض می کنیم که دو تانکر شماره یک و دو با هم منفجر شده اند. زیرا اگر تانکر شماره یک با تانکر شماره $k$(عددی زوج است) منفجر شده باشد، آنگاه تمام تانکر های با شماره $2$ تا $k$ منفجر شده اند، و ما فرض می کنیم که تانکر شماره $1$ با $2$, $3$ با $4$،...، $k-1$ با $k$ منفجر شده اند. پس تعداد حالت ها می شود: $F(n-2)$

پس نتیجه می گیریم که:

$F(n)=F(n-1)+F(n-2)$

که با توجه به اینکه $F(2)=2$ و $F(3)=3$ نتیجه می گیریم که $F(10)=89$

Comments

@Elyas1 در واقع جواب، جمله یازدهم دنباله فیبوناچی است در حالت کلی$F(n) =f_{n+1}$

---

@amir7788 چقدر جالب.پس اگر $x_1= \frac{1+ \sqrt{5} }{2}$ و $x_2= \frac{1- \sqrt{5} }{2}$  آنگاه داریم:

$F(n)= \frac{x_{1}^{n+1}-x_{2}^{n+1}}{ \sqrt{5}}$

---

@احمدرضا137 پاسخ برایتان نامفهوم است؟ اگر هست بگویید تا بیشتر توضیح دهم.

---

@Elyas1 با توجه به اینکه کاربر پرسش‌کننده مدت زیادی است که فعال نیست و پیش‌تر زحمت تایپ و ارسال پاسخ‌تان را کشیده‌بودید حیف دانستم که پست را حذف کنم چون زحمت شما به هدر می‌رفت، لذا پست را باز و پاسخ شما را بازنمایش و امتیاز دادم. پرسش‌های دیگری که به دلیل عدم تلاش و تمایل پرسش‌کننده بسته بودند و پاسخی نداشتند را پنهان کردم.