پرسش

با سلام و خسته نباشید.
نشان دهید در یك جمع 6نفره یا حداقل3نفر هستند كه همدیگر را2به2 میشناسند یا 3نفر هستند كه 2به2یكدیگر را نمیشناسند.

پاسخ

سلام
یكی از آن شش نفر را در نظر بگیرید. او را فرد 1 می نامیم. بقیه را 2 تا 6 می نامیم. فرد 1 بعضی از افراد 2 تا 6 را می شناسد و برخی را نمی شناسد.
فرض كنیم او x نفر را بشناسد و y نفر را نشناسد. پس x+y=5 . حال دو حالت را در نظر می گیریم:
حالت 1: x>y بنابر این x لا اقل مساوی 3 خواهد بود. یعنی فرد 1 لااقل 3 نفر را میشناسد. اگر این سه نفر را الف، ب و ج بنامیم، دو حالت متصور است:
حالت1-1: الف، ب و ج هیچ كدام همدیگر را نمی شناسند، كه در این صورت خواسته مساله برقرار است.
حالت 1-2: دو تا از آنها، مثلا الف و ب هم را می شناسند، اما فرد 1 نیز این دو را می شناسد. پس این سه نفر، یعنی فرد 1، الف و ب همدیگر را می شناسند. پس خواسته مساله برقرار است.
حالت 2: x حالت2-1: الف، ب و ج هر سه همدیگر را می شناسند، كه در این صورت خواسته مساله برقرار است.
حالت 1-2: دو تا از آنها، مثلا الف و ب هم را نمی شناسند، اما فرد 1 نیز این دو را نمی شناسد. پس این سه نفر، یعنی فرد 1، الف و ب هیچ كدام، همدیگر را نمی شناسند. پس خواسته مساله برقرار است.
بنا بر این، در هر یك از حالتها، یكی از دو وضعیت مطلوب مساله رخ می دهد.

اشاره: این مساله را به این صورت نیز می توان بیان كرد: در 2-رنگ آمیزی یالهای یك گراف كامل 6 راسی، یك زیرگراف كامل 3 راسی با یالهای یك رنگ یافت می شود.
این حكم، با استفاده از اعداد رمزی به این ترتیب بیان می شود: R(3,3)=6

موفق باشید