پاسخ : ماراتن المپیاد ریاضی- کاری از دوره طلا
سوال آخر برای شب زنده دارها: IMO Shortlist 2009
همه ی اعداد طبیعی n را بیابید که دنباله ی
از اعداد طبیعی موجود باشد که
برای هر
یک نکته: یک چیزی توی این سواله خیلی نامردیه!!!! شب بر شما خوش! :4:
اول از همه یه تشکر درست حسابی از goldeneagle عزیز که این سوالو گذاشتن و این وقت شب مارو شب زنده دار نگه داشتن
البته اون نکته یا راهنمایی آخر کارتون منو خیلی دلگرم کرد برای حل مساله :21:
حل کردم و امیدوارم جوب نزده باشم
این وقت شب جوب خور هممون بالاست
ابتدا با یذره ساده کردن جمله عمومی دنباله بازگشتی و جمع کردن طرفین با 1 این شکلی میشه:
حالا میخوایم ثابت کنیم که
زوج اند.برهان خلف: فرض کنید مثلا
فرد باشه.داریم:
که تناقض است.با فرض اینکه
هم فرده به طور مشابه به تناقض میرسیم.بنابراین داریم(k هایی را میتوانیم در نظر بگیریم که در اشتراک راه طی شده برای اثبات زوج بودن
هستند) :
حال برای ساده سازی در نوشتن فرض کنید
.بنابراین داریم:
حال فرض کنید از تمامی جوابهای طبیعی و زوج این معادله جوابی را در نظر بگیریم که در آن
مینیمال باشد.
بنابراین k زوج است.
پس توانستیم از جواب (m,n) به جواب (n,k) برسیم و چون
مینیمال است پس فقط سه حالت داریم:
1)
.یعنی:
که این با زوج بودن n متناقض است.پس این حالت رد شد.
2)
.یعنی:
که هیچ جواب طبیعی ای ندارد.
3)
.یعنی اینکه از روی هر دو
میتوانیم نامتناهی تا جمله دیگر با m+n بزرگتر مثل
بسازیم و از آنجا که تعداد مقسوم علیه های
متناهی است ولی با توجه به فرض داریم
و این یعنی تناقض!!!
و این یعنی هیچ جواب
زوج و طبیعی
ای وجود ندارد که
.
حال باید n ای را بیابیم که هیچ دو عضو متوالی و
زوجی از آن رابطه
را نداشته باشند.حال ثابت میکنیم حداکثر طول دنباله n=4 است.فرض کنید طول دنباله ای 5 باشد.که اگر در معادلات بالا قرار دهیم k=3 آنگاه به این نتیجه میرسیم که
هر دو زوج هستند!و با توجه به معادلات بالا به تناقض میرسیم!!!(چون همانطور که گفته شد این معادله بالا به ازای m,n زوج جواب ندارد.پس دنباله به طول 3 خواهد شد!!)بنابراین جمله پنجمی وجود ندارد و پس
است.حال دنباله ای با طول 4 میسازیم!
میدانیم در دنباله ای به طول 4 داریم:
برای اینکه بتوانیم حدسی برای ساخت دنباله بدست بیاوریم باید داشته باشیم:
میدانیم که
همزمان نباید زوج باشند!اگر
فرد باشد آنگاه
نیز فرد خواهد بود.سعی میکنیم با همین حدس فرد بود هر دوی اینها جلو برویم.
بنابراین
زوج خواهد شد.از مقادیر ابتدایی شروع میکنیم.
که تناقض است!
حال با امتحان کردن
و بدست آوردن بقیه جملات دنباله,اولین
قابل قبولی که بدست می آید(
ای که جملات
طبیعی باشند)
است.پس این دنباله به صورت زیر است:
این دنباله بدست آمده کوچکترین دنباله است(و از 1384 اش برمیاد که سوال پیشنهادی جهانی ایران توی(2005 میلادی=1384 خورشیدی) IMO 2005 باشه
ایران از این خز بازیا ممکنه در بیاره
)
البته واضحه وقتی برای n=4 دنباله ساخته شده با حذف کردن جمله 4 ام این دنباله؛دنباله ای برای n=3 ساخته میشود و با حذف دو جمله آخر دنباله ای برای n=2 و با حذف سه جمله آخر دنباله ای برای n=1 ساخته میشود که در جمله عمومی دنباله نیز صدق میکند...پس اگر مجموعه جواب را
بنامیم آنگاه خواهیم داشت:
سوال خیلی قشنگی بود.بازم دم این چهار تا طلایی گرم که از این سوالای باحال میذارن
دیگه صبح شده.ما شب زنده دارا بگیریم بخوابیم