لم:هر دو تا بازیکن با هم در حد اکثر یک تورنمنت هستند.حال فرض کنید با حداکثر 10 تورنمنت مساله حل شود.در این صورت گروهی هست که طبق اصل لانه کبوتری حداقل 11 بازیکن در این تورنمنت حضور داشتند.اسم این گروه را بگذارید تاکسی.حال طبق فرض مساله کسی مثل راننده هست که در تاکسی شرکت نکرده و چون باید با افراد تاکسی بازی کند.باید با هر کدام از آنها در یک تورنمنت شرکت کند وچون افراد تاکسی با هم نمیتوانند در تورنمنتی دیگر باشند راننده در هرتورنمنت با حداکثر یک نفر از تاکسی مسابقه میدهد پس در حداقل 11 تورنمنت شرکت کرده.تناقض.پس حداقل 11 تورنمنت داریم.

سلام .
سوال گفته اگر یالهای یک گراف کامل 101 راسی رو به چند تا زیر گراف کامل که هر کدوم حداکثر 100 راس دارن افراز کنیم ، حداقل تعداد این زیرگراف ها 11 تاست ( از 10 تا بیشتره )

ثابت میکنیم نمیشه یالهای گراف کامل 101 راسی رو به 10 تا زیرگراف کامل با حداکثر 100 راس افراز کرد. در اونصورت ثابت میشه حداقل 11 تا زیرگراف مورد نیازه .
فرض کنیم تونستیم به 10 تا زیرگراف افراز کنیم . میدونیم هر راس توی دو تا زیر گراف مشاهده میشه ( چرا ؟ چون میدونیم هر زیرگراف شامل حداکثر 100 تا راسه و حداقل یک راس درونش نیست ، پس برای اینکه یال های بین اون راسی که داخل زیرگراف نیست و رئوس داخل زیرگراف نمایش داده بشه باید توی یک زیرگراف دیگه دو سر اون یال ها بیان پس اگه یه راس فقط توی یک زیرگراف بیان ، یالی که به راس خارج داره هرگز نمایش داده نمیشه. ) و هیچ دو راسی توی دو تا زیر گراف با هم نبودن . ( به عبارتی هر دو راسی دقیقن توی یک زیر گراف با هم هستن )

بنابراین اگر زیر گرافی حاوی b راس باشه. میدونیم به ازای هر راس شماره i ( محدوده i یک تا b ) از این زیرگراف ، یک زیرگراف منحصرن متعلق به همون راس وجود داره ( چون میدونیم به جز زیرگراف b راسی ، در حداقل یک زیر گراف دیگه هم اومده و همینطور دو تا راس از این زیر گراف b راسی نمیتونن توی یک زیر گراف دیگه با هم باشن چون هر یال باید یک بار بیاد نه بیشتر )

بنابراین اگر یک زیرگراف b راسی داشته باشیم ، میتونیم مطمئن باشیم حداقل کل زیرگراف ها برابر b + 1 است.
خب اگر 10 تا زیرگراف باشن ، مسلمه که هر زیرگراف حداکثر میتونه 9 تا راس رو شامل بشه .
با این حساب حداکثر 90 راس توی زیرگراف ها به کار رفتن در حالی که 101 راس داریم .

پس 10 تا زیرگراف برای افراز این گراف کمه و حداقل 11 تا زیرگراف لازمه .