المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۵۵

در یک مهمانی ۱۴ نفر حضور دارند. می‌دانیم که هر یک از مهمان‌ها حداکثر ۴ نفر از مهمان‌های دیگر را می‌شناسد٬ و نیز می‌دانیم که بین این افراد دقیقا ۲۱ مورد آشنایی دو جانبه وجود دارد.

آیا حالتی وجود دارد که این افراد بتوانند به گونه‌ای دور یک میز بنشینند که هر کس نفر سمت راست خود را بشناسد و با نفر سمت چپ نا‌آشنا باشد؟

پاسخ

در شکل زیر یال‌های جهت‌دار نشانگر آشنایی‌های یک‌طرفه و یال‌های بدون جهت نشانگر آشنایی‌های دو طرفه است.


ابزار صفحه