حل مسالهي چهارشنبهي سوم
قبل از اين كه به جواب مسألهي اين هفته بپردازيم بايد بگم كه در مورد سوال دو هفته قبل مشكلي در مورد خوشتعريف بودن تابع معرفي شده در راه حل CppBuilder2006 بوجود اومده بود كه با توضيحات (خصوصي(!)) ايشون من متوجه اشتباهم شدم و پست مربوط به جواب مسألهي چهارشنبهي دوم يعني
کد:
http://forum.p30world.com/showpost.php?p=4049984&postcount=79
رو ويرايش كردم. از ايشون به خاطر توضيحات كاملشون متشكرم. و اما مسألهي هفته قبل:
من هم مانند CppBuilder2006 در پست
کد:
http://forum.p30world.com/showpost.php?p=4052634&postcount=86
مسأله رو بصورت تركيبياتي حل كرده بودم. ولي متوجه شدم كه در شمارش، تعداد جوابهايي كه چند بار شمرده ميشن خيلي زياده.
از طرفي اگه در فرمول بدست اومده به جاي n عدد 2 رو قرار بديم ميبينيم كه جواب منفي ميشه.
ولي راه حل از اين قراره.
ابتدا چند نكته رو در نظر ميگيريم
فرض كنيد
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
يك nتايي خوب باشه. از اين به بعد اين n تايي رو بصورت صعودي مرتب شده در نظر ميگيريم. نشون ميديم كه اگر aiها مساوي نباشن آنگاه a1=1.
چون
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
پس
بنابراين
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
. پس a1=1.
از طرفي اگه a_i ها مساوي باشن بايد همشون 2 باشن. حالا اگه n زوج باشه n-تايياي كه همه مولفههاش 2 باشن نميتونه يك n-تايي خوب باشه و اگه n فرد باشه چنين n-تايياي حتما خوب هست. از اين به بعد فرض ميكنيم كه a_iها با هم مساوي نيستن.
حالا ميخوايم با استفاده از استقراء ثابت كنيم كه همه n-تاييهايي خوب به صورت
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
هستن.
پايهي استقراء : به راحتي بررسي ميشود.
فرض استقراء : n-1n-1 تايي
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
تنها n-1-تايي خوب به طور مرتب صعودي است.
ميخواهيم نشان دهيم كه هر n-تايي خوب به طور صعودي مرتب شده مانند
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
به صورت
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
است. ادعا ميكنيم كه n-1-تايي
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
خوب است.
واضح است كه
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
. فرض كنيم B زيرمجموعهاي از
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
باشد و
اگر n-1 در B باشد آنگاه
پس
كه ممكن نيست.
و اگر n-1 در B نباشد آنگاه
كه باز هم غيرممكن است. بنابراين
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
يك n-1-تايي خوب است. و حكم بدين ترتيب اثبات ميشود.
در نهايت تعداد n-تاييهي خوب اين طور بدست ميآيد كه اگر n زوج باشد برابر n و اگر n فرد باشد برابر n+1.