ناشناس
سوال 176463
به نام خدا <br />سلام <br />در یك مسابقه همرا با جایزه كه مهلت آن تمام نشده پرسیده شده :<br />اثبات كنید: از هر6 نفرآدم حتما یا 3 نفر وجود دارند كه 2 به 2 باهم دوستند یاحتما 3 نفر وجود دارند كه2 به 2با هم دوست نییستند منمی خواهم در این مسابقه شركت كنم<br /> و با اینكه دیپلم راضی دارم سر در نمی آورم<br />با تشكر<br /> - دیپلم
ثبت پاسخ جدید
برای ثبت پاسخ، لطفا وارد حساب کاربری خود شوید.
پاسخ‌ها
1 پاسخبا سلام و عرض پوزش از تأخیر در پاسخ به سؤال شما
می‌توان 6 نفر را 6 رأس گراف در نظر گرفت. اگر دو نفر با هم دوست باشند دو رأس نظیرشان در گراف را به هم وصل می‌کنیم. حالا سؤال شما به این صورت تعبیر می‌شود که در هر گراف با 6 رأس یک مثلث وجود دارد و یا مکمل گراف مثلث دارد. چون هر رأس گراف 6 رأسی می‌تواند به حداکثر 5 رأس دیگر گراف متصل باشد، طبق اصل لانه کبوتری درجه هر رأس گراف در خود گراف یا مکمل آن حداقل 3 است. اگر گراف رأسی چون x از درجه حداقل 3 داشته باشد، اگر دو تا از همسایه‌های رأس x به هم وصل باشند این دو رأس با رأس x یک مثلث در گراف می‌سازند. اگر هیچ‌یک از همسایه‌ها به هم وصل نباشند، 3 تا ازاین همسایه‌ها در مکمل گراف مثلث می‌سازند. اگر گراف رأسی از درجه حداقل 3 نداشته باشد، رئوس مکمل گراف از درجه حداقل 3 هستند و استدلال بالا را می‌توان برای مکمل گراف تکرار کرد.
موفق باشید.
می‌توان 6 نفر را 6 رأس گراف در نظر گرفت. اگر دو نفر با هم دوست باشند دو رأس نظیرشان در گراف را به هم وصل می‌کنیم. حالا سؤال شما به این صورت تعبیر می‌شود که در هر گراف با 6 رأس یک مثلث وجود دارد و یا مکمل گراف مثلث دارد. چون هر رأس گراف 6 رأسی می‌تواند به حداکثر 5 رأس دیگر گراف متصل باشد، طبق اصل لانه کبوتری درجه هر رأس گراف در خود گراف یا مکمل آن حداقل 3 است. اگر گراف رأسی چون x از درجه حداقل 3 داشته باشد، اگر دو تا از همسایه‌های رأس x به هم وصل باشند این دو رأس با رأس x یک مثلث در گراف می‌سازند. اگر هیچ‌یک از همسایه‌ها به هم وصل نباشند، 3 تا ازاین همسایه‌ها در مکمل گراف مثلث می‌سازند. اگر گراف رأسی از درجه حداقل 3 نداشته باشد، رئوس مکمل گراف از درجه حداقل 3 هستند و استدلال بالا را می‌توان برای مکمل گراف تکرار کرد.
موفق باشید.