• اگر سمپادی هستی همین الان عضو شو :
    ثبت نام عضویت

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

  • شروع کننده موضوع
  • #1

سمپادک

کاربر جدید
ارسال‌ها
2
امتیاز
1
نام مرکز سمپاد
فرزانگان 1
شهر
تهران
سال فارغ التحصیلی
1406
سلام به همگی چند وقت پیش از یه کتابی سوال ترکیبیاتی رو دیدم چند روز هم روش فکر کردم ولی نتونستم حلش کنم متن سوال به این شکل بود

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

سمپادک

کاربر جدید
ارسال‌ها
2
امتیاز
1
نام مرکز سمپاد
فرزانگان 1
شهر
تهران
سال فارغ التحصیلی
1406
سلام به همگی چند وقت پیش از یه کتابی سوال ترکیبیاتی رو دیدم چند روز هم روش فکر کردم ولی نتونستم حلش کنم متن سوال به این شکل بود


اگر کسی راه حل این رو بگه ممنون میشم
این رو توی یکی انجمن ها پرسیده بودند برای من هم جالب شد:-j
 

MorteZ

کاربر نیمه‌حرفه‌ای
ارسال‌ها
191
امتیاز
7,179
نام مرکز سمپاد
هاشمی نژاد ۱
شهر
مشهد
سال فارغ التحصیلی
1394
دانشگاه
امیرکبیر
رشته دانشگاه
مهندسی کامپیوتر - نرم افزار
سلام به همگی چند وقت پیش از یه کتابی سوال ترکیبیاتی رو دیدم چند روز هم روش فکر کردم ولی نتونستم حلش کنم متن سوال به این شکل بود


اگر کسی راه حل این رو بگه ممنون میشم
سلام، اگه مجموعه رو 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نفر.
چون فاصله افتاده و نوشتاری توضیح دادم ممکنه مبهم بوده باشه. اگر بود بپرس که واضح تر بگم، البته امیدوارم اشتباه حل نکرده باشم.
 
  • لایک
امتیازات: Blank
بالا