سلام دوستان...
کسی میتونه راهنمایی کنه که چطور میشه با استفاده از اصل لانه کبوتری نشان داد که در یک کلاس n نفره، حداقل ۲ نفر وجود دارند که تعداد دوستانشان باهم برابر است؟
در یک کلاس n نفره اگر مجموعه افراد را بصورت زیر نشان بدیم:
[tex]P=\left \{ P_{1},P_{2},\cdots ,P_{n} \right \}[/tex] که [tex]\left | P \right |=n[/tex] می باشد
و تعداد دوست های یک نفر در این کلاس هم از مجموعه زیر انتخاب می شود:
[tex]F=\left \{ 1,2,\cdots ,n-1 \right \}[/tex] که [tex]\left | F \right |=n-1[/tex] می باشد
پس طبق اصل لانه کبوتری چون [tex]\left | P \right |> \left | F \right |[/tex] است اگر افراد مجموعه P از مقادیر
مجموعه F انتخاب کنند حداقل دو نفر یک مقدار را انتخاب کرده اند / یعنی حداقل ۲ نفر وجود دارند که تعداد دوستانشان باهم برابر است.
(01 تير 1391 02:00 ب.ظ)unique_as14 نوشته شده توسط: [ -> ]در یک کلاس n نفره اگر مجموعه افراد را بصورت زیر نشان بدیم:
[tex]P=\left \{ P_{1},P_{2},\cdots ,P_{n} \right \}[/tex] که [tex]\left | P \right |=n[/tex] می باشد
و تعداد دوست های یک نفر در این کلاس هم از مجموعه زیر انتخاب می شود:
[tex]F=\left \{ 1,2,\cdots ,n-1 \right \}[/tex] که [tex]\left | F \right |=n-1[/tex] می باشد
پس طبق اصل لانه کبوتری چون [tex]\left | P \right |> \left | F \right |[/tex] است اگر افراد مجموعه P از مقادیر
مجموعه F انتخاب کنند حداقل دو نفر یک مقدار را انتخاب کرده اند / یعنی حداقل ۲ نفر وجود دارند که تعداد دوستانشان باهم برابر است.
البته به نظرم تعداد دوست های هر نفر می تونه از مجموعه ی [tex]F = \left \{ 0,1,2,...,n-2 \right \}[/tex]
هم در نظر گرفته بشه که بازم [tex]|F|=n-1[/tex].
(01 تير 1391 02:19 ب.ظ)riga نوشته شده توسط: [ -> ]البته به نظرم تعداد دوست های هر نفر می تونه از مجموعه ی [tex]F = \left \{ 0,1,2,...,n-2 \right \}[/tex]
هم در نظر گرفته بشه که بازم [tex]|F|=n-1[/tex].
درسته
اگر فرض کنیم هر نفر حداقل یک دوست داره میشه مجموعه [tex]F=\left \{ 1,2,\cdots ,n-1 \right \}[/tex] و اگر کسی بدون دوست هم باشه میشه [tex]F = \left \{ 0,1,2,...,n-2 \right \}[/tex] که هر دو درسته ولی مهم اینه که [tex]\left | F \right |=n-1[/tex]
سلام. مجموعه از 0 تا n-1 هست. یعنی n عضو. ولی امکان نداره هردو حالت 0 و n-1 عضو با هم اتفاق نمی افته. یعنی اگه یه عضو n-1 دوست داشته باشه هیچ عضوی پیدا نمیشه که دوستی نداشته باشه. چون حداقل با اون عضو خاص دوسته. اگرم عضو صفر دوسته داشته باشیم مسلماً عضو n-1 دوسته نداریم. پس در هردوحالت n عضو با n-1 حالت داریم.
با توجه به اینکه n نفر n راس یک گراف را تشکیل میدهند و رابطه دوستی تشکیل یک گراف ساده میدهد ----->
درجه رئوس این گراف از 0 تا n-1 هست با توجه به اینکه درجه رئوس گراف ساده شامل یک عضو تکراری هست در نتیجه اگر تعداد اعضا را n لانه در نظر بگیریم و رابطه دوستی را تعداد کبوترها حکم ثابت میشود .
این سوالها رو از چند روش میشه حل کرد اینهم مدل گرافیش .