شب 6

سلام شاز.

اول راه سوال شب 5 رو میگم. اگه نمیخواین اسپویل شه این قسمتو اسکیپ کنین.

فرض کنین میز 2n+1 نفری باشه. با استقرا ثابت میکنیم به ازای هر k بین 1 تا n+1، بعد از گذشت یه تعداد حرکت، یا 2k تا کارت با شماره 1 تا k هیچ کدوم دوتاشون دست یه نفر نیست (دقیقن 2k تا جا اشغال کردن) یا اینکه حکم سوال (دوتا کارت با شماره برابر دست یه نفر باشن) نتیحه شده. به ازای k=1 حکم درسته، چون یا دوتا کارت 1 دست یه نفرن، یا اینکه دست دو نفرن :3

حالا برای k ثابت میکنیم. طبق فرض استقرا روی k-1، بعد از یه تعداد حرکت یا حکم نتیجه شده که حله یا اینکه تمام کارت های 1 تا k-1 دست آدمای مختلفه. این کارتای 1 تا k-1 هر مرحله دقیقن یکی شیفت سمت راست میخورن؛ چون از بقیه کارتا اکیدن کوچیکترن و به هم دیگه هم برخورد نمیکنن چون فاصله هاشون حفظ میشه. حالا یه کارت k رو در نظر بگیرید. آدمی که این کارته رو داره اول یه تعداد کارت 1 تا k-1 میان پیشش و میرن و بالاخره یا کارت k دیگه میاد پیشش که حله، یا اینکه یه کارت بزرگتر از k میاد پیشش. در اینصورت آدمه کارت k اشو میده بغلی و این کارت k عه هر دفعه به بغلی داده میشه؛ چون آدم کناری طبق فرض استقرا نهایتن یه دونه کارت کمتر از k داره که توی اون حرکت پاسش میده به بغلی خودش و اون یکی کارتش حتمن یا k عه که حله یا بزرگتر از k عه و بازم این پاس دادن ادامه پیدا میکنه. به این ترتیب اون همه 2k تا کارت 1 تا 2k هم دقیقن 2k تا آدم اشغال میکنن و گام استقرا ثابت میشه.

حالا طبق چیزی که اثبات کردیم به ازای k=n+1، چون نمیشه همه 2n+2 تا کارت دست آدمای مختلف باشه، پس حالت دیگه درسته که یعنی حکم مسئله ثابت شده :#

 

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

G یه گراف دوبخشی کامله که هر بخشش n تا راس دارن. F یه گراف دو بخشیه که بخش بالا n تا راس داره بخش پایین 2n-1 راس که راس i ام از بخش بالا به راس های 1 تا 2i-1 از پایین وصله. ثابت کنید به ازای هر x از 1 تا n، تعداد تطابق های x یالی تو G و F برابره.

 

نویسنده : امید آزادی (سوال امشب از کلباسه)