ماراتن ترکیبیات
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
[center:779badbf43]2[HIGHLIGHT=#ff0000]5[/HIGHLIGHT][/center:779badbf43]
من یک راهنمایی دیگه می کنم ، اگه بازم حل نشد، خودم حلشو می نویسم
راهنمایی دوم: از یک راس دلخواه از یک دور دلخواه شروع به شماره گذاری راس ها کنید تا به خودش برگردید.(شکل اجتماعی از دورها است. که هیچ مسیری بین آنها نیست) یعنی هر دو تا دور که به هم متصل باشند (بدون گذر از دور دیگری) اشتراک ناتهی از رئوس دارند.
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
جواب سوال 25
[center:c7bb0b68f3]
[/center:c7bb0b68f3]پاسخ سوال بیست و پنجم:
اول چند تا نکته :
1-هر راسی قسمتی از حداقل یک دور است (چون وقتی راه بین دو راس یک طرفه شد ، توانستیم از راه دیگری از راس دوم به راس اول بیاییم)
2-شکل اجتماعی از چند دور است. و بین دور ها چیز دیگری نیست. (یعنی یال (ها) یی وجود ندارند که دو تا دور را از هم جدا کنند.)
یعنی شکل این طوری نداریم که مسیر قرمز رنگ (که دور هم نیست) دو تا دور را از هم جدا کرده باشد. (این رو خودتون تحقیق کنید، آسونه)
این دور(ها) را دور(های) دوم می نامیم.
با توجه به روش ما می توان از هر نقطه داخل دور اول به هر نقطه ای در هر کدام از دورهای دوم رفت و بالعکس
همچنین می توان از هر نقطه داخل یک دور دوم به دورهای سوم متصل به آن رفت و بالعکس.
..... و این روند همینطور ادامه می یابد
پس اگر از نقطه ای در دور اول شروع کنیم می توانیم به همه ی نقاط دیگر برویم.
و اگر از نقطه ای خارج از دور اول شروع کنیم ، می توانیم به دور اول بیاییم ، پس می توانیم به هر نقطه ی دیگر برویم.
ببخشید که خوب توضیح ندادم و طولانی هم شد. واقعا ایده ی ساده ای داره ولی نوشتنش سخته!
اگه جایی ابهام داشتید بگید تا با کمال میل بیشتر توضیح بدم.
بریم سوال بعد؟
[center:c7bb0b68f3]
اول چند تا نکته :
1-هر راسی قسمتی از حداقل یک دور است (چون وقتی راه بین دو راس یک طرفه شد ، توانستیم از راه دیگری از راس دوم به راس اول بیاییم)
2-شکل اجتماعی از چند دور است. و بین دور ها چیز دیگری نیست. (یعنی یال (ها) یی وجود ندارند که دو تا دور را از هم جدا کنند.)
حالا یک دور انتخاب می کنیم. (بهش می گیم دور اول) و از یک راس دلخواه آن شروع به شماره گذاری می کنیم. اولین راس را 1 می نامیم و همینطور می رویم تا k. هر دور دیگری را که در نظر بگیریم ، قسمتی از آن که از دور اول خارج است یکی از 3 حالت زیر را دارد:
- یا به دو تا از راس های دور اول وصل است
- یا فقط به یکی از راس های دور اول وصل است
- یا به دور دیگری وصل است و به دور اول وصل نیست (با توجه به همبند بودن گراف)
این دور(ها) را دور(های) دوم می نامیم.
حال به سراغ دورهایی می رویم که فقط به یکی از راسهای دور اول وصل هستند. این دورها حداقل دو راس دارند که به راس داخل دور اول وصل است. آنها را از یک طرف به صورت دلخواه شماره گذاری می کنیم. به این ها هم دور(های) دوم می گوییم.
اگر دوری به دور اول وصل نباشد یا به دوری از نوع دوم وصل است یا نیست. اگر وصل باشد ، آن را مانند دو مرحله قبل جهت دار می کنیم و دور نوع سوم می نامیم و همین روند را ادامه می دهیم تا به دورهای s_ام(یعنی آخرین شماره دورها) برسیم
. با توجه به روش ما می توان از هر نقطه داخل دور اول به هر نقطه ای در هر کدام از دورهای دوم رفت و بالعکس
همچنین می توان از هر نقطه داخل یک دور دوم به دورهای سوم متصل به آن رفت و بالعکس.
..... و این روند همینطور ادامه می یابد
پس اگر از نقطه ای در دور اول شروع کنیم می توانیم به همه ی نقاط دیگر برویم.
و اگر از نقطه ای خارج از دور اول شروع کنیم ، می توانیم به دور اول بیاییم ، پس می توانیم به هر نقطه ی دیگر برویم.
ببخشید که خوب توضیح ندادم و طولانی هم شد. واقعا ایده ی ساده ای داره ولی نوشتنش سخته!
اگه جایی ابهام داشتید بگید تا با کمال میل بیشتر توضیح بدم.
بریم سوال بعد؟
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
سوال بیست و ششم
[center:98be581130]
[/center:98be581130]سوال بیست و ششم:
الف)اگر ترتیب مد نظر باشد ، تعداد طرقی که می توان 17 را به صورت حاصل جمعی از 1 ها و 2 ها نوشت بیابید.(جواب بازگشتی یک کمی آشنا نیست؟)
ب) مسئله را تعمیم دهید و تعداد طرق نوشتن n را به صورت حاصل جمعی از 1 تا n-1 بیابید. (می توانید رابطه بازگشتی را بنویسید و حل کنید.)
[center:98be581130]
الف)اگر ترتیب مد نظر باشد ، تعداد طرقی که می توان 17 را به صورت حاصل جمعی از 1 ها و 2 ها نوشت بیابید.(جواب بازگشتی یک کمی آشنا نیست؟)
ب) مسئله را تعمیم دهید و تعداد طرق نوشتن n را به صورت حاصل جمعی از 1 تا n-1 بیابید. (می توانید رابطه بازگشتی را بنویسید و حل کنید.)
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
[center:d2d7051086]
[/center:d2d7051086]آفرین بر شما!
اما لطفا سعی کنید بازگشتی حلش کنید
قسمت دوم سوال اینجوری حل شدنی نیست!
این سوال رو هم ببینید:
[hr:d2d7051086]نکته ای راجع به مثلث خیام - پاسکال
[hr:d2d7051086]
اما لطفا سعی کنید بازگشتی حلش کنید
قسمت دوم سوال اینجوری حل شدنی نیست!
این سوال رو هم ببینید:
[hr:d2d7051086]نکته ای راجع به مثلث خیام - پاسکال
[hr:d2d7051086]
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
[center:1c24a18005]2[HIGHLIGHT=#002060]6[/HIGHLIGHT][/center:1c24a18005][center:1c24a18005]
[/center:1c24a18005]از راهنمایی گذشته دیگه
دارم جوابشو می ذارم.
روی اولین عدد متمرکز شوید.
اگر تا 5 دقیقه دیگه جوابشو ندید ، تایپ کردن من تمام می شود
Olympiad گفت
درباره ي رابطه بازگتي قسمت ب يه راهنمايي كنيد لطفا
دارم جوابشو می ذارم.
روی اولین عدد متمرکز شوید.
اگر تا 5 دقیقه دیگه جوابشو ندید ، تایپ کردن من تمام می شود
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
پاسخ سوال بیست و ششم
الف) فرض کنید تعداد راههای نوشتن n یه صورت حاصل جمعی از 1 ها و 2 ها را با a[SUB]n[/SUB] نشان دهیم. در این صورت داریم : a[SUB]n[/SUB]=a[SUB]n-1[/SUB]+a[SUB]n-2[/SUB]
a[SUB]1[/SUB]=1 و a[SUB]2[/SUB]=2 . یعنی فیبوناچی است. a[SUB]n[/SUB]=F[SUB]n-1[/SUB]
ب) روی اولین عددی که نوشتیم متمرکز شوید. این عدد بین 1 تا n-1 است پس اگر تعداد حالات در این قسمت از مسئله را با b[SUB]n[/SUB] نمایش دهیم داریم:
. می دانیم b[SUB]1[/SUB]=1 و b[SUB]2[/SUB]=2=2b[SUB]1 [/SUB]با ادامه ی همین روند داریم : b[SUB]3[/SUB]=3b[SUB]1[/SUB] و b[SUB]4[/SUB]=6b[SUB]1[/SUB] و b[SUB]5[/SUB]=12b[SUB]1[/SUB] و در نتیجه برای n ها از بعد از این داریم : b[SUB]n[/SUB]=2b[SUB]n-1[/SUB] پس می توانیم بنویسیم:
[/center:b78326c326]
همین بنده خدایی که همه اش سوال می ذاره و جواب نمی گیره گفت
[center:b78326c326]
[/center:b78326c326]سوال بیست و ششم:
الف)اگر ترتیب مد نظر باشد ، تعداد طرقی که می توان 17 را به صورت حاصل جمعی از 1 ها و 2 ها نوشت بیابید.(جواب بازگشتی یک کمی آشنا نیست؟)
ب) مسئله را تعمیم دهید و تعداد طرق نوشتن n را به صورت حاصل جمعی از 1 تا n-1 بیابید. (می توانید رابطه بازگشتی را بنویسید و حل کنید.)
الف)اگر ترتیب مد نظر باشد ، تعداد طرقی که می توان 17 را به صورت حاصل جمعی از 1 ها و 2 ها نوشت بیابید.(جواب بازگشتی یک کمی آشنا نیست؟)
ب) مسئله را تعمیم دهید و تعداد طرق نوشتن n را به صورت حاصل جمعی از 1 تا n-1 بیابید. (می توانید رابطه بازگشتی را بنویسید و حل کنید.)
a[SUB]1[/SUB]=1 و a[SUB]2[/SUB]=2 . یعنی فیبوناچی است. a[SUB]n[/SUB]=F[SUB]n-1[/SUB]
ب) روی اولین عددی که نوشتیم متمرکز شوید. این عدد بین 1 تا n-1 است پس اگر تعداد حالات در این قسمت از مسئله را با b[SUB]n[/SUB] نمایش دهیم داریم:
ولی می توانیم کمی کلی تر هم بنویسیم:
[center:b78326c326]
حالا دیگه هر طور که خودتون راحتید. قسمت ب این سوال تالیفی بود!
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
حالا انتظار دارم این سوال را به راحتی حل کنید: ftopicp-19715.html#19715