به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
+1 امتیاز
27 بازدید
در دبیرستان و دانشگاه توسط mansour (382 امتیاز)

در اتاقی که حداقل دو نفر حضور دارند ثابت کنید که دو نفر از میان آنها هستند که تعداد دوستان یکسانی دارند( دوستی همواره دو طرفه است)

1 پاسخ

+1 امتیاز
توسط قاسم شبرنگ (2,373 امتیاز)
ویرایش شده توسط قاسم شبرنگ
 
بهترین پاسخ

افراد را رأسهای یک گراف و رابطه دوستی را یال نشان دهید.فرض کنید در جه رأسها به صورت زیر باشد:

$d_1 \leq d_2 \leq ... \leq d_n$

می دانیم که در یک گراف ساده ( بدون طوقه و هر دو رآس حداکثر با یک یال وصلند ) مجموح یالها حداکثر $ \binom{n}{2} $ است.حالا اگر هیچ دو نفری تعداد دوستان یکسانی نداشته باشند پس:

$0 \leq d_1< d_2< ...< d_n \Rightarrow d_1+d_2+...+d_n \geq 1+2+...+(n-1)= \frac{(n-1)n}{2} $

بنابر این باید مجموع رأسها مساوی $ \frac{n(n-1)}{2} $ باشد یعنی گراف کامل است یعنی درجۀ هر رآس $ \frac{n-1}{2} $ است و چون ($n \geq 2$) پس حداقل دو نفر هستند که تعداد دوستانشان برابر و مساوی $ \frac{n-1}{2} $ است که تناقض است.

$ \Box $


حمایت مالی

کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
...