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

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

الف) با دانستن تمام روابط آشنایی در یک جمع $n$ نفره٬ دایره‌های دوبه‌دو نامتقاطع $C_n ,...,C_2,C_1$ در صفحه کشیده‌اند به طوری که دایره‌های $C_i$ و $C_j$ متداخل‌اند اگر و فقط اگر بین فرد $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$. ثابت کنید با دانستن تمام آشنایی‌های این جمع٬ می‌توان دایره‌های دوبه‌دو نامتقاطع $C_n ,...,C_2,C_1$ در صفحه کشید به طوری که دایره‌های $C_i$ و $C_j$ متداخل‌ باشند اگر و فقط اگر بین فرد $i$ و فرد $j$ در آن جمع رابطه‌ی آشنایی وجود داشته باشد.

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

{{ :سوالات_المپیاد:مرحله‌ی_دوم:دوره‌ی_۱۸:k.png?nolink |}}


  * [[سوال هفت|سوال قبل]]