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

[behrooz1373]

یه سوال ترکیبیات)
200 تیم با هم مسابقه می دهند می دانیم در هر روز هر تیم دقیقا یک بازی داشته است ثابت کنید بعد از روز ششم می توان 34 تیم را پیدا کرد که هیچ کدام با هم بازی نکرده اند.

 

[Goharshady]

 

[Goharshady]

 

[Goharshady]

 

[mohammad2004]

سلام.
توی مثال نقض اولتون ، تیم 1 با 200 و 199 و 198 و 2 و 3 و 4 بازی کرده و تیم 5 با 2 و 3 و 4 و 6 و 7 و 8
اگه تیم 1 و 5 رو انتخاب کنیم که مشکلی پیش نمیاد . پس نمیشه گفت از هر 7 تیم حداکثر یکی رو میشه انتخاب کرد

مثال نقض دوم هم غلطه چون اصلا نمیتونیم 7 تایی کامل داشته باشیم . چون توی فرض داشتیم هر تیم هر روز دقیقا یک بازی انجام داده. پس گراف باید به 6 تا تطابق افراز بشه و چون 7 تایی ها کامل هستن پس خود 7 تایی ها هم باید به تطابق ها افراز بشن اما شرط لازم و کافی برای افراز گراف به تطابق ها ، زوج بودن تعداد راس هاست که اینجا تعداد رئوس هر دسته 7 تاس.

نکته جالب اینجاست که این سوال درسته و سوال آسونی هم نیست.

 

[behrooz1373]

تعمیم این سوال صفحه275 سوال30 از فصل 11 کتاب علیپور است.

 

[Goharshady]

سلام.
مثال نقض دوم هم غلطه چون اصلا نمیتونیم 7 تایی کامل داشته باشیم . چون توی فرض داشتیم هر تیم هر روز دقیقا یک بازی انجام داده. پس گراف باید به 6 تا تطابق افراز بشه و چون 7 تایی ها کامل هستن پس خود 7 تایی ها هم باید به تطابق ها افراز بشن اما شرط لازم و کافی برای افراز گراف به تطابق ها ، زوج بودن تعداد راس هاست که اینجا تعداد رئوس هر دسته 7 تاس.

نکته جالب اینجاست که این سوال درسته و سوال آسونی هم نیست.

حق با شماست
معذرت می خواهم.

 

[navidjalalmanesh]

گراف این بازی ها رو بسازید (درجه هر راس 6 هست ) بعدش به راحتی ثابت می شه که یه مجموعه مستقل به اندازه بیشتر یا مساوی 200/6 وجود داره که همون حکم مسئله است .

روش اثبات وجود این مجموعه هم اینه که مثلا فرض کنید درجه هر راس این گراف t باشه در این صورت در هر مرحله یه راس دلخواه برمی داریم و همه راس های متصل به اون رو دور می ریزیم .

اگر تا k مرحله این کار را انجام بدیم حداقل n-tk راس باقی می مونه (در هر مرحله حداکثر t راس می ره بیرون ) که این نتیجه می ده مجموعه مستقلی با اندازه n/t در گراف وجود داره و حکم ثابت می شه !

 

[mohammad2004]

چطوری نوییییییید؟؟؟ شناختی؟؟

راستی جوابت غلطه

وقتی که همسایه های یه راسو میریزیم بیرون خود راس رو هم باید بریزیم بیرون پس 7/200 تا راسو میده که کران بدیه

تو اصلا از فرض اینکه هر تیم هر روز دقیقا یه بازی داره استفاده نمیکنی

 

[navidjalalmanesh]

اشتباه می کنی . هر دفعه که من یه راس انتخاب می کنم فقط همسایه هاش رو بیرون می کنم . به خودش کاری ندارم چون توی مجموعه باقی مونده یه راس تنها به حساب می یاد که برای ما هیچ ضرری نداره !

از این فرض که هر تیم هر روز دقیقا یه بازی داره نتیجه می شه که درجه هر راس دقیقا 6 است که توی اثباتم ازش استفاده کردم !

 

[mohammad2004]

نوید از تو بعیده

وقتی همسایه های یه راسو حذف میکنی و انتخابش میکنی که دیگه نمیتونی انتخاب کنی اون راسو. مثل این میمونه که اون راس رو هم حذف کنی

تازه بدون شرط هر تیم هر روز دقیقا یه مسابقه این سوال مثال نقض داره. با درست کردن گراف های 7 راسی کامل

 

[navidjalalmanesh]

نمی دونم چطوری توضیح بدم . ببین هدف من اینه که از گراف اصلی شروع کنم و در هر مرحله از این گراف یه تعدادی راس نامطلوب حذف کنم به طوری که گراف باقیمونده مون یه مجموعه مستقل باشه .

من وقتی یه راس رو انتخاب می کنم در واقع یعنی فرض می کنم اون راس تو مجموعه مستقل ام باشه . پس تمام همسایه هاش رو باید بریزم دور اما خودش رو که نباید بریزم دور چون فرض کردم تو مجموعه مستقل پایانی اون راس وجود داره .

بعد هم بدیهی یه که توی هر مرحله راس هایی که حذف می شن اون راس هایی نیستن که قبلا انتخابشون کردم . پس اثبات کاملا درسته .

پیشنهاد می کنم یه بار دیگه اثباتم رو بخونی .

 

[mohammad2004]

نوید

خوب اینطوری از بین هر 7 راس داری یکیو انتخاب میکنی.
تازه اگه راهت درست باشه و از فرض هر تیم هر روز دقیقا یه بازی داره استفاده نکنی راهت باید واسه هر گرافی که درجه هر راسش 6 هست هم درست باشه.
اما اگه گرافو به 27 تا گراف 7 راسی کامل و یه گراف 11 راسی 6 منتظم تقسیم کنیم حد اکثر میتونیم 27+6 راس انتخاب کنیم.
من راهتو خوندم اولین راهی هم که خودم واسه این سوال گفتم همین بود اما بعد فهمیدم غلطه و راهمو درست کردم

.