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

[سمپادک]

سلام به همگی چند وقت پیش از یه کتابی سوال ترکیبیاتی رو دیدم چند روز هم روش فکر کردم ولی نتونستم حلش کنم متن سوال به این شکل بود

گروهی شامل k نفر داریم که تعداد دوست های هر نفر با بقیه برابر است میدانیم مجموعه ای شامل بیش از نصف این افراد هستند که ۲ به ۲ با یکدیگر دوستند ثابت کنید همه این افراد باهم دوستند (دقت کنید دوستی رابطه ای دو طرف است)

اگر کسی راه حل این رو بگه ممنون میشم

 

[سمپادک]

سلام به همگی چند وقت پیش از یه کتابی سوال ترکیبیاتی رو دیدم چند روز هم روش فکر کردم ولی نتونستم حلش کنم متن سوال به این شکل بود


اگر کسی راه حل این رو بگه ممنون میشم

این رو توی یکی انجمن ها پرسیده بودند برای من هم جالب شد

 

[----]

سلام به همگی چند وقت پیش از یه کتابی سوال ترکیبیاتی رو دیدم چند روز هم روش فکر کردم ولی نتونستم حلش کنم متن سوال به این شکل بود


اگر کسی راه حل این رو بگه ممنون میشم

سلام، اگه مجموعه رو 2k نفر در نظر بگیریم. طبق فرض سوال یک گروه k+1 ای داریم که دو به دو با هم دوستن ینی میشه هر کدوم k تا رابطه دوستی دارن حداقل. پس تمام 2k نفر باید k تا رابطه داشته باشن (۱) . حالا هرکدوم از اون k-1 رو در نظر بگیریم( اونایی که الزاما ۲ به ۲ دوست نیستن.) حالا میخوایم ثابت کنیم که این عضو خارجی که اسمشو میذاریم b باید با تک تک k+1 تا دوست باشه، به چه شکل؟
طبق (۱) باید b با k تا دوست باشه ولی چون اعضای بیرونی k-1 هستش پس حداقل با یکی از اون k+1 ای های داخلی دوسته. اسم این راس داخلی رو میذاریم a. حالا که با a دوسته، پس حداقل تعداد روابط تمام اعضا حالا میشه k+1 ای که تعداد روابط a عه. پس با این حساب اون راس b حالا باید با حداقل یکی دیگه از رئوس داخلی هم دوست باشه که به همین شکل تا اخر بریم ثابت میشه که b با همه ی مجموعه داخلی دوسته. پس حالا مجموعه داخلیمون به جای k+1 راس، k+2 راس داره که همه با هم دوستن. به همین ترتیب برای بقیه k-2 تا راس هم ثابت میشه که هر کدوم با همه دوستن و در نهایت مجموعه داخلیمون میشه همون 2kنفر.
چون فاصله افتاده و نوشتاری توضیح دادم ممکنه مبهم بوده باشه. اگر بود بپرس که واضح تر بگم، البته امیدوارم اشتباه حل نکرده باشم.