Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

دایره‌های عجیب

در یک جمع n نفره٬ هر دو نفر یا با هم آشنا هستند یا نیستند. فرض کنید افراد با شماره‌های ۲٬۱ تا n نام‌گذاری شده‌اند و آشنایی رابطه‌ای دو طرفه است؛ یعنی اگر i با j آشنا باشد حتماً j هم با i آشناست.

الف) با دانستن تمام روابط آشنایی در یک جمع n نفره٬ دایره‌های دوبه‌دو نامتقاطع Cn,...,C2,C1 در صفحه کشیده‌اند به طوری که دایره‌های Ci و Cj متداخل‌اند اگر و فقط اگر بین فرد i و فرد j رابطه‌ی آشنایی وجود داشته باشد. ثابت کنید در این جمع٬ به ازای هر چهار فرد متمایزِ a٬ b٬ c و d٬ که a با b٬ b با c و c با d آشناست٬ حتماً یا a با c آشناست یا b با d.

ب) جمعی را در نظر بگیرید که در آن به ازای هر چهار فرد متمایز a٬ b٬ c و d٬ که a با b٬ b با c و c با d آشناست٬ حتماً یا a با c آشناست یا b با d. ثابت کنید با دانستن تمام آشنایی‌های این جمع٬ می‌توان دایره‌های دوبه‌دو نامتقاطع Cn,...,C2,C1 در صفحه کشید به طوری که دایره‌های Ci و Cj متداخل‌ باشند اگر و فقط اگر بین فرد i و فرد j در آن جمع رابطه‌ی آشنایی وجود داشته باشد.

برای مثال در شکل زیر افرادی که با پاره‌خط به هم وصل شده‌اند با هم آشنا هستند و دایره‌ها نیز بر همین اساس رسم شده‌اند.


ابزار صفحه