سوال ترکیبیات

[8149]

m زیر مجموعه k عضوی از مجموعه x داریم . ثابت کنید هر عضو X رو میشه با آبی و قرمز طوری رنگ کرد که حداکثر (m/2^(k-1 تا از زیر مجموعه هامون تکرنگ باشند .( همه اغضا یکرنگ باشند .)
ترکیبیات . ص 43 . س 28.4.2
آخر راه حل رو که واگذار کرده به خواننده نمیفهمم.

 

[آبی]

پاسخ : تورو خدا یکی جواب بده

منم دقیقا همین مشکلو دارم. اگه یکی پیدا بشه که جواب بده خیلی خوب میشه!!!

 

[erfan_ashorian]

پاسخ : تورو خدا یکی جواب بده

سلام!اقا من با 2 راه حل کردم جفتشو میگم!
1)(اولیش که راه علیپوره!)خب من کامل میگم ببینید میاییم یه جدول 2به توان Nدر Mمیکشیم حالا این 2به توان Nتعداد راه های رنگ کردن کل مجموعس!حالا میدانیم که تعداد حالت هایی که تو اون این زیر مجموعه تکرنگه 2به توان N-K+1 هست چرا چون به 2 طریق میشه این مجموعه را رنگ کرد بقیه اعداد را هم هر کدام به 2 طریق!حالا پس تعداد یک های جدول برابر 2به توان N-K+1ضرب در Mمیباشد حالا از سطر ها نگاه کنید قضیه را نگاه کنید ثابت میکنم حداقل یه سطر هست که توش کمتر از Mتقسیم بر 2به توان K-1هست فرض کنید این طوری نباشه پس حداقل تو جدول باید Mتقسیم بر 2به توان K-1(کل پعبارت )ضرب در 2 به توان Nتا یک داشته باشیم که میشه 2 به توان N-K+1ضرب در Mکه باید از این بیشتر باشه پس به تناقض برخوردیم چون ما قبلا به دست اوورده بودیم که از این کمتره!
2)(راه خویشتن!)خب اگه الان سوال براتون سوخت من این راهو الان ناقص میگم روش فکر کنید بعد کاملشو میگم!راهش اینه که میاییم یه جدول Nدر Mمیکشیم بعد برای هر زیر مجموعه اگه یه عضوی تو اون زیر مجموعه بود یک در غیر این صورت صفر!حالا بیاید از عضو اول برید پایین هر بار هر عضو دو بار رنگ کنید ببینید چه اتفاقی میافته!(به نظر من این راه قشنگ تره )تا خواستید بگید تا راه دومو کامل بگم