سوال شب هفتم

سلام سلام صد تا سلام.
باور کردنش سخته ولی یه هفته گذشته و ما هنوز داریم ادامه میدیم :)

خب اول می پردازیم به راه حل سوال دیشب. کسانی که می خوان سوال براشون نسوزه این قسمت را نخونن.

واضحه که تعداد تطابق های x تایی توی گراف G که برابر هستش با c(n, x) ^ 2 (انتخاب x از n به توان دو) ضرب در x فاکتوریل. حالا می خواهیم ثابت کنیم تعداد تطابق های x تایی گراف F هم همین قدره. فرض می کنیم جواب مسئله مون هستش (f(n, x. حالا می خواهیم یه رابطه بازگشتی برای f پیدا کنیم. با کمی تلاش به رابطه بازگشتی زیر می رسیم:

(f(n, x) = f(n - 1, x) + f(n - 1, x - 1) * (2n - x

برای اثبات رابطه بازگشتی بالا میاییم راس n ام را در نظر می گیریم. یا با هیچ کس تطابق داده نمیشه که در این صورت میشه (f(n - 1, x. یا به یه راس دیگه تطابق داده میشه. در این صورت میاییم اول به (f(n - 1, x - 1 طریق یه تطابق x - 1 تایی توی n - 1 نفر اول پیدا می کنیم. حالا چون n به همه 2n - 1 راس قسمت دیگه وصله و از بین اونا دقیقا x - 1 تاشون با راس دیگه تطابق داده شدن, راس n ام 2n - x انتخاب برای تطبیق داره. پس رابطه بازگشتی بالا ثابت میشه. حالا با استفاده از استقرا بر روی n و مقدار کمی جبر می توانید ثابت کنید که (f(n, x برابر است با c(n, x) ^ 2 (انتخاب x از n به توان دو) ضرب در x فاکتوریل. بنابر این مسئله ثابت می شود. 3:

حالا سوال امشب:

در مدرسه ای n دانش آموز وجود دارند. هر دانش آموز در تعدادی گروه عضو است. اگر دو گروه دو دانش آموز مشترک داشته باشند آنگاه تعداد اعضایشان متفاوت است. ثابت کنید تعداد گروه ها از (n-1)*(n-1) کمتر است. ( گروه یک نفره نداریم )

راستی بچه ها یه خبر دیگه ای هم براتون دارم. ما واسه راحت تر کردن ارتباط خودتون با خودمون و خودتون با خودتون تصمیم گرفتیم از یه اپ پیام رسانی به اسم discord استفاده کنیم. هم اینکه فیلتر نیست هم اینکه طبقه بندی خوبی داره و هم اینکه جذابه :))

از این به بعد سوالای شب و یه سری چیزای دیگه رو اونجا میذاریم. خلاصه که جمع بشید اینجا پرچم شازو ببریم بالا :*

بعد که اپو نصب کردین با این لینکه بیاید تو.

بای بای :)

حمیدرضا کلباسی