المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۵۵

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

پاسخ

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

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


ابزار صفحه