Processing math: 100%

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۸:سوال ۵۵

سوال ۵۵

در یک مهمانی ۷ نفر حضور دارند. می‌دانیم که هر نفر حداقل با سه نفر دیگر آشناست. آیا همواره می‌توان این ۷ نفر را به گونه‌ای دور یک میز نشاند که هر دو نفری که در کنار هم نشسته‌اند باهم آشنا باشند؟

پاسخ

فرض می‌کنیم a با همه‌ی افراد٬c،b و d دو به دو باهم و f،e و g نیز دو به دو باهم آشنا باشند و هیچ آشنایی دیگری موجود نباشد.

بدون این که به کلیت مسئله لطمه‌ای وارد شود فرض می‌کنیم سمت چپ a نفر b باشد، دراین صورت سمت چپ b یا باید c نشسته باشد و یا d. در حالت اول نفر بعدی (نفر چهارم)d و در حالت دوم نفر بعدی c خواهد شد٬ ولی معلوم است که فردی که با d( یا c) آشنا باشد پیدا نمی‌شود تا در جایگاه پنجم بنشانیم.


ابزار صفحه