مرحله ۲ اولا
يكشنبه, ۱۷ ارديبهشت ۱۳۸۵، ۱۲:۵۶ ب.ظ
۱) اونهایی که f_0=0 هست که تابلوئه آینه‌ای هستن. چون اگه f_1=a باشه اونوقت دنبالمون میشه عین فیبوناچی که فقط هر عدد ضریب a گرفته. که میشه اینو با استقرا یا کلی چیز دیگه اثبات کرد.
بقیه‌ی دنباله‌ها رو میشه فرض کرد که f_0 همه بیشتر از صفره, چون اگه اینجوری نباشه کافیه همه‌ی دنباله رو در ۱- ضرب کرد و رابطه‌ی آینه‌ای بودن یا نبودن همچنان برقرار میماند. حالا خود اینها میشن دو دسته:
دسته‌ی اول: اونهایی هستن که f_1 کمتر از صفره. برای اینها کافیه f_1 و f_-1 رو در نظر بگیرید و به تناقض برسونید.
دسته‌ی دوم: اونهایی که f_1 بزرگتر از صفره. برای اینها کافیه اولین i رو در نظر بگیرید که منفی شده. باز دو حالت پیش میاد:
اولین i بعد از ۱ و -۱ باشه: اگه فرمولش رو بنویسید میبینید که مجبور میشه دنباله شامل یکدونه صفر باشه. و ما چند خط بالاتر ثابت کردیم که با شروع از ۰ به یک دنباله‌ی آینه‌ای میرسیم که البته نسبت به جایگاه ۰ آینه‌ای هستن. برای همین دنباله‌ی ما از f_0 نمیتونه آینه‌ای بشه.
اولین i خود ۱ و -۱ باشه: که در این صورت اگه فرمول رو بنویسید می‌رسید به f_1= - f_-1 که نتیچه میده i=2*j و با استقرا ثابت میشه که این هم حالتی از جوابه.
و اینجوری ثابت میشه دنباله‌هایی که یا f_0=0 با f_1=2*f_j هست جواب مسئله است.
۲) این جور سوال‌ها که بر میگردن به روابط بازگشتی بهشون میگن dynamic. مثلا توی این سوال وقتی می‌خوایم c_i,j رو حساب کنیم, باید ببینیم که چطور مسئله‌ی حل از i تا j رو به حل یه تعداد r تا k تبدیل کنیم. البته باید همیشه توجه کنید که توی دور نیفتیم, یعنی از حل i,j دوباره نرسیم به خود i,j. البته در این سوال‌ها یک سری حالت اولیه هم در نظر گرفته میشه که جوابشون بدیهی تلقی میشه, مثلا در این سوال c_i,i صفر در نظر گرفته میشه. در این سوال هم کافیه توجه کنیم که در حالت بهینه برای حل i,j ما آخرین حرکتمان جوش دادن دو تکه میله هست که یکی شامل میله‌های از i تا k هست و اون یکی شامل از k تا j که k میتونه از i+1 تا j-1 باشه. پس c_i,j مساوی خواهد بود با مینیمم
c_i,k + c_k+1,j + w_i,k + w_k+1,j
که در اون k از i+1 تا j-1 هست و w_x,y هم به معنای جمع وزن میله‌های از x تا y هست.
برای حساب کردن c_1,n هم کافیه یه جدولn*n بکشید که در اون درایه‌ی x,y نشون‌دهنده‌ی c_x,y باشه و حالا اول همه‌ی اونهایی رو بدست بیارید که y-x=1 هست. بعد اونهایی که y-x=2 هست, همیونجور ادامه بدید تا اونهایی که مساوی n هست.
۳) بیاید برای هر شهر یک تابع f در نظر بگیرید که f شهر a میشه اون مجاوریش که اگه جاده‌ی بین a و اون مجاور رو حذف کنیم, زیر کشور اون مجاوره بیشتر از 2n/3 بشه. واضحه که f یه نفر بیشتر از یه شهر نیست. حالا سوال اینه که آیا شهری هست که f نداشته باشه؟ (چون اگه همه‌ی رئوس f داشته باشند که بدیهیه مسئله جواب نداره و اگه یه راس بدون f پیدا بشه, کافیه که اون یالی رو حذف کنیم که زیر کشور تشکیل شده‌ی دارای مجاورش ماکزیمم راس را داشته باشد)
خوب حالا برهان خلف می‌زنیم, اگه همه f داشته باشند, کافیه یه راس a رو در نظر بگیریم. حالا میریم سراغ f_a و بعد سراغ f_f_a و همینطور ادامه میدیم و هر دفعه میریم به f راسی که داخلش هستیم. این مثل حرکت روی جاده‌ها میمونه. ار اونجایی که توی جاده‌هامون دور نداریم(بین هر دو شهر دقیقا یک مسیر وجود داره) و تعداد راس‌ها هم متناهیه, پس یه زمانی از جاده‌ای که اومدیم دوباره برمی‌گردیم. خوب این یعنی هر ور جاده 2n/3 شهر داره که تناقضه
این یه روش استقرا داره که میگه اگه طی مراحلمون به n(طول جایگشت) رسیدیم که در مرحله‌ی بعدی n به اول جایگشت میاد و ازگردونه حذف میشه و بقیه هم طبق استقرا حل میشند. و اگه هم هیچوقت n نیاد که خوب مسلما هیچوقت عددی که در اول جایگشت هست هم استفاده نخواهد شد برای همین هیچ عیبی نداره اگه جای n رو با اون عدده عوض شده فرض کنیم. و حالا هم با استقرا باز به نقره‌ای خواهیم رسید.
این سوال یه روش با حال هم داره که میاد میگه به هر حایگشت یک عدد در مبنای ۲ میدیم. اینجوری که اگر عدد سمت راست ۱ بود, بیت سمت راست رو میذاریم ۱ وگرنه ۰. برای بقیه هم همینطور, اگه نفر i ام از سمت راست جایگشت برابر با i بود, بیت i ام از راست ۱ وگرنه ۰ است. حالا نکته اینجان که با یک عملیات روی جایگشت اگر نفر سمت راست ۱ بوده باشد که عدد ما هیچ تغییری نمی‌کند وگرنه عددمان بزرگ می‌شود(خودتان اثبات کنید) و چون عددمان از ۲ به توان n نمیتواند بیشتر شود لذا زمانی محبور است به جایگشت نقره‌ای برسد.
۵)خب این با قضیه‌ی هال که بدیهیه. بدونه اون هم با استقرا میشه گفت. اون جعبه‌ای که یدونه داره که واضحه باید از اون جعبه همون مهرهه انتخاب بشه, حالا فرض کنید اسم اون جعبه a باشه و مهره‌ی داخل اون b باشه. حالا که ما b رو انتخاب کردیم, باید ببینیم که کدوم جعبه b داشته(اگه هیچ کس دیگه‌ای نباشه که خوب رسیدیم به حالتی که از همه دقیقا ۲ تا داریم و با روشی شبیه به همین حله.) میایم اون جعبه‌ای که b رو داشت در نظر میگیریم و فرض میکنیم که b از توش حذف شده. حالا مثل اینه که رسیده باشیم به حالت فرض استقرا و همینطور ادامه میدیم تا تموم بشه.
بقیه‌ی دنباله‌ها رو میشه فرض کرد که f_0 همه بیشتر از صفره, چون اگه اینجوری نباشه کافیه همه‌ی دنباله رو در ۱- ضرب کرد و رابطه‌ی آینه‌ای بودن یا نبودن همچنان برقرار میماند. حالا خود اینها میشن دو دسته:
دسته‌ی اول: اونهایی هستن که f_1 کمتر از صفره. برای اینها کافیه f_1 و f_-1 رو در نظر بگیرید و به تناقض برسونید.
دسته‌ی دوم: اونهایی که f_1 بزرگتر از صفره. برای اینها کافیه اولین i رو در نظر بگیرید که منفی شده. باز دو حالت پیش میاد:
اولین i بعد از ۱ و -۱ باشه: اگه فرمولش رو بنویسید میبینید که مجبور میشه دنباله شامل یکدونه صفر باشه. و ما چند خط بالاتر ثابت کردیم که با شروع از ۰ به یک دنباله‌ی آینه‌ای میرسیم که البته نسبت به جایگاه ۰ آینه‌ای هستن. برای همین دنباله‌ی ما از f_0 نمیتونه آینه‌ای بشه.
اولین i خود ۱ و -۱ باشه: که در این صورت اگه فرمول رو بنویسید می‌رسید به f_1= - f_-1 که نتیچه میده i=2*j و با استقرا ثابت میشه که این هم حالتی از جوابه.
و اینجوری ثابت میشه دنباله‌هایی که یا f_0=0 با f_1=2*f_j هست جواب مسئله است.
۲) این جور سوال‌ها که بر میگردن به روابط بازگشتی بهشون میگن dynamic. مثلا توی این سوال وقتی می‌خوایم c_i,j رو حساب کنیم, باید ببینیم که چطور مسئله‌ی حل از i تا j رو به حل یه تعداد r تا k تبدیل کنیم. البته باید همیشه توجه کنید که توی دور نیفتیم, یعنی از حل i,j دوباره نرسیم به خود i,j. البته در این سوال‌ها یک سری حالت اولیه هم در نظر گرفته میشه که جوابشون بدیهی تلقی میشه, مثلا در این سوال c_i,i صفر در نظر گرفته میشه. در این سوال هم کافیه توجه کنیم که در حالت بهینه برای حل i,j ما آخرین حرکتمان جوش دادن دو تکه میله هست که یکی شامل میله‌های از i تا k هست و اون یکی شامل از k تا j که k میتونه از i+1 تا j-1 باشه. پس c_i,j مساوی خواهد بود با مینیمم
c_i,k + c_k+1,j + w_i,k + w_k+1,j
که در اون k از i+1 تا j-1 هست و w_x,y هم به معنای جمع وزن میله‌های از x تا y هست.
برای حساب کردن c_1,n هم کافیه یه جدولn*n بکشید که در اون درایه‌ی x,y نشون‌دهنده‌ی c_x,y باشه و حالا اول همه‌ی اونهایی رو بدست بیارید که y-x=1 هست. بعد اونهایی که y-x=2 هست, همیونجور ادامه بدید تا اونهایی که مساوی n هست.
۳) بیاید برای هر شهر یک تابع f در نظر بگیرید که f شهر a میشه اون مجاوریش که اگه جاده‌ی بین a و اون مجاور رو حذف کنیم, زیر کشور اون مجاوره بیشتر از 2n/3 بشه. واضحه که f یه نفر بیشتر از یه شهر نیست. حالا سوال اینه که آیا شهری هست که f نداشته باشه؟ (چون اگه همه‌ی رئوس f داشته باشند که بدیهیه مسئله جواب نداره و اگه یه راس بدون f پیدا بشه, کافیه که اون یالی رو حذف کنیم که زیر کشور تشکیل شده‌ی دارای مجاورش ماکزیمم راس را داشته باشد)
خوب حالا برهان خلف می‌زنیم, اگه همه f داشته باشند, کافیه یه راس a رو در نظر بگیریم. حالا میریم سراغ f_a و بعد سراغ f_f_a و همینطور ادامه میدیم و هر دفعه میریم به f راسی که داخلش هستیم. این مثل حرکت روی جاده‌ها میمونه. ار اونجایی که توی جاده‌هامون دور نداریم(بین هر دو شهر دقیقا یک مسیر وجود داره) و تعداد راس‌ها هم متناهیه, پس یه زمانی از جاده‌ای که اومدیم دوباره برمی‌گردیم. خوب این یعنی هر ور جاده 2n/3 شهر داره که تناقضه
این یه روش استقرا داره که میگه اگه طی مراحلمون به n(طول جایگشت) رسیدیم که در مرحله‌ی بعدی n به اول جایگشت میاد و ازگردونه حذف میشه و بقیه هم طبق استقرا حل میشند. و اگه هم هیچوقت n نیاد که خوب مسلما هیچوقت عددی که در اول جایگشت هست هم استفاده نخواهد شد برای همین هیچ عیبی نداره اگه جای n رو با اون عدده عوض شده فرض کنیم. و حالا هم با استقرا باز به نقره‌ای خواهیم رسید.
این سوال یه روش با حال هم داره که میاد میگه به هر حایگشت یک عدد در مبنای ۲ میدیم. اینجوری که اگر عدد سمت راست ۱ بود, بیت سمت راست رو میذاریم ۱ وگرنه ۰. برای بقیه هم همینطور, اگه نفر i ام از سمت راست جایگشت برابر با i بود, بیت i ام از راست ۱ وگرنه ۰ است. حالا نکته اینجان که با یک عملیات روی جایگشت اگر نفر سمت راست ۱ بوده باشد که عدد ما هیچ تغییری نمی‌کند وگرنه عددمان بزرگ می‌شود(خودتان اثبات کنید) و چون عددمان از ۲ به توان n نمیتواند بیشتر شود لذا زمانی محبور است به جایگشت نقره‌ای برسد.
۵)خب این با قضیه‌ی هال که بدیهیه. بدونه اون هم با استقرا میشه گفت. اون جعبه‌ای که یدونه داره که واضحه باید از اون جعبه همون مهرهه انتخاب بشه, حالا فرض کنید اسم اون جعبه a باشه و مهره‌ی داخل اون b باشه. حالا که ما b رو انتخاب کردیم, باید ببینیم که کدوم جعبه b داشته(اگه هیچ کس دیگه‌ای نباشه که خوب رسیدیم به حالتی که از همه دقیقا ۲ تا داریم و با روشی شبیه به همین حله.) میایم اون جعبه‌ای که b رو داشت در نظر میگیریم و فرض میکنیم که b از توش حذف شده. حالا مثل اینه که رسیده باشیم به حالت فرض استقرا و همینطور ادامه میدیم تا تموم بشه.
- ۸۵/۰۲/۱۷