تپلوس ها موجوداتی هستند که بین هر جفت از آنها یک رابطه ي دو طرفهي دوستی یا دشمنی برقرار است. ویژگی جالب این موجودات این است که به ازای هر سه تپلوس دلخواهی٬ یا هر سه با هم دوست اند یا دو نفرشان که با هم دوست اند٬ هر دو با نفر سوم دشمن اند.
با توجه به توضیحات بالا به ۲ سوال زیر پاسخ دهید:
جمشید سیاره ای متعلق به تپلوس ها کشف کرده است که در آن دقیقا ۱۲ رابطهي دشمنی وجود دارد. حداقل چند تپلوس در این سیاره زندگی می کند؟
پاسخ
گزینهی ۴ درست است.
فرض کنید گرافی داریم که راسهایش تپلوسها و یالهای آن، رابطهی دشمنی بین دو نفر هستند. در این صورت شرط سوال بدین معنی است که در هر سهتایی زوج یال وجود دارد.
با این تعاریف، ثابت میکنیم با ۶ راس نمیتوان ۱۲ یال در گراف داشت و با ۷ راس یک مثال میآوریم.
برهان خلف. فرض کنید با ۶ راس بتوان چنین گرافی ساخت. مکمل گراف را در نظر بگیرید. در این گراف در هر سهتایی فرد یال داریم (چرا؟).
مثال برای ۷ راس: گرافی کامل دوبخشی با بخشهای ۳ و ۴ عضوی در نظر بگیرید. این گراف شرایط مسئله را دارد و دارای ۱۲ یال است.
تحقیقات اخیر جمشید نشان می دهد که در سیاره ای جدید٬ ۹ تپلوس با نام های $T_۱$ تا $T_۹$ زندگی میکنند. همچنین او فهمیده است که $T_۱$ و $T_۲$ با هم دشمن٬ $T_۳$ و $T_۴$ با هم دشمن و $T_۴$ و $T_۵$ هم با هم دشمناند. با این اطلاعات روابط دوستی و دشمنی بین این ۹ تپلوس به چند شکل مختلف می تواند باشد؟
پاسخ
گزینهی ۲ درست است.
اگر وجود و یا عدم وجود یالهای بین $(T_1,T_3 ),(T_1,T_6 ),(T_1,T_7 ),(T_1,T_8 ),(T_1,T_9)$ مشخص گردند بقیه یالها به صورت یکتا تعیین خواهند شد. این یالها نیز هرکدام به صورت مستقل ۲ حالت دارند. در نتیجه تعداد کل حالات برابر ۳۲ خواهد بود.