یک گراف ۹ یالی جهت دار مطابق شکل آمده در پرسش داریم. چند مسیر متفاوت با شروع از گرهٔ $A$ به درازای ۹ داریم؟ تکرار در مسیر مجاز است.

Question

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

راهنمایی: اختلاف رقم دهگان و يکان جواب کمتر و يا مساوی ۱ است.

Comments

کپی شده است،اکنون اصلاح میگردد

---

راس های وسط اضلاع مثلث بزرگ رو خلاف جهت ساعت به ترتیب  a,b,c نامگذاری کن به طوری که راس وسط ضلع پایین مثلث a باشد.
در واقع ما حرکت خود را از a شروع می کنیم چون مجبوریم از A به a بریم و ما انتخاب دیگه ای نداریم.
از این به بعد حرکات رو یک چرخه در نظر بگیر که ما در ان از a به b از b به c و از c دوباره به a میرسیم.
و فقط حق انتخاب ما این است که مثلا در حرکاتمان از a به b ما یک لیتر سوخت مصرف کنیم یا دو لیتر

با این راهنمایی فک کنم بتونی حلش کنی.

---

فکر کنم روشتان با روش پاسخ داده شده متفاوت است ولی با آنچه گفته اید بازهم نمیتوانم حل کنم.اگر میشود پاسختان را بفرستید

Answer 1

گراف کاربر mdgi را در نظر بگیرید. حالت ها رو به دو قسمت تقسیم میکنیم:

1) حالت هایی که سپهر در نقاط B D F به گردش خود پایان بدهد.

2) حالت هایی که در نقاط A C E به گردش خود پایان بدهد.

حالت اول در این حالت ما چرخه ای داریم: B به D از D به F و از F به B که ما باید یا با مصرف دو لیتر یا با مصرف یه لیتر بنزین هر یک از مرحله های چرخه را طی کنیم (شروع حرکت را از B در نظر بگیرید با 8 لیتر بنزین)با توجه به اینکه حرکت ما در این سه نقطه هم پایان میگیرد پس تعداد حالات برابر است با افراز های مرتب عدد 8 با توجه که جمعوند ها آن یا 1 یا 2 باشند.

که افراز های مرتب عدد 8 با توجه که جمعوند ها آن یا 1 یا 2 باشند برابر است با 34

حالت دوم

همان شرایط حالت اول را در نظر بگیرید با این تفاوت که فرض میکنیم به جای 8 لیتر 7 لیتر بنزین داریم زیرا اخرین لیتر بنزین صرف این میشود که ما از نقاط B یا D یا F به نقاط A یا C یا E برویم.

پس تعداد این حالت هم برابر با افراز مرتب عدد 7 با توجه که جمعوند ها آن یا 1 یا 2 باشند که برابر 21 است.

پس جواب برابر است با: 21+34=55

Comments

یک مشکلی برایم پیش آمده است.
به عنوان مثال افراز عدد 8 میشود 4تا 2 که اگه ازB به D میشود دو لیتر و از D به F میشود دو لیتر و از F به B میشود دو لیتر.یک دو لیتر دیگه میماند با سه خیابان،که نمیشود از سه خیابان گذشت.ممنون میشم بگید چه چیزی رو اشتباه میکنم.(همان شکل mdgi را در نظر گرفتم)

---

اگه سوالتون رو درست متوجه شده باشم باید بگم لازم نیس حتما سپهر تمام خیابان ها رو بگرده فقط میخواد به گردش بپردازه.
و افراز عدد 8 به چهار تا 2 حالتیه که هیچ وقت ما مستقیم از B به D  یا از D به F یا از F به B  نمی رویم یعنی آن دو لیتری که شما فرمودید اینگونه مصرف میشود: از (B به C و از C به D )یعنی ما در گردش خود اصلا وارد اون سه خیابان نمیشویم.

---

من سوال رو اشتباه متوجه شدم.ممنون

Answer 2

فرض کنم منظور از $f(B,n)$ تعداد حالاتی باشد که سپهر می‌تواند با $n$ لیتر بنزین و شروع از نقطه $B$ در شهر گردش کند. پس داریم $$f(B,n)=f(c,n-1)+f(D,n-1)=f(D,n-2)+f(D,n-1)$$

اما با توجه به متقارن بودن شکل، همواره $f(B,k)=f(D,k)=f(F,k)$. پس $$f(B,n)=f(B,n-2)+f(B,n-1).$$ از طرفی $f(B,1)=2, f(B,2)=3$. پس دنباله زیر را داریم: $$2,3,5,8,13,21,34,55,89,\ldots $$ حال جواب سوال میشود $f(B,8)$ یعنی 55.