فهرست مندرجات
سوالات ۳۲ و ۳۳
تپلوس‌ها موجوداتی هستند که بین هر جفت از آنها یک رابطه‌ی دو طرفه‌ی دوستی یا دشمنی برقرار است. ویژگی جالب این موجودات این است که به ازای هر سه تپلوس دلخواهی، یا هر سه با هم دوست‌اند یا دو نفرشان که با هم دوست‌اند٬ هر دو با نفر سوم دشمن‌اند.
با توجه به توضیحات بالا به ۲ سوال زیر پاسخ دهید:
سوال ۳۲
جمشید سیاره‌ای متعلق به تپلوس‌ها کشف کرده است که در آن دقیقا ۱۲ رابطه‌ی دشمنی وجود دارد. حداقل چند تپلوس در این سیاره زندگی می‌کنند؟
- ۹
- ۶
- ۵
- ۷
- ۸
راهنمایی
گرافی در نظر گیرید که هر تپلوس یک راس آن باشد. هر یال دشمنی را قرمز و هر یال دوستی را آبی در نظر می‌گیریم. رنگ‌های یال‌های زیر‌گراف‌های القایی سه راسی گراف مورد نظر به چه صورت‌هایی می‌تواند باشد؟
راهنمایی
دقت کنید گراف ساخته شده نمی‌تواند مثلث قرمز داشته باشد. پس زیرگراف فراگیر با یال‌های قرمز حداکثر چند یال می‌تواند داشته باشد؟
راهنمایی
برای مثال عدد ۷، تپلوس‌ها را به دو گروه ۳ و ۴ نفره افراز کنید.
پاسخ
گزینه‌ی ۴ درست است.
فرض کنید گرافی داریم که راس‌هایش تپلوس‌ها و یال‌های آن، رابطه‌ی دشمنی بین دو نفر هستند. در این صورت شرط سوال بدین معنی است که در هر سه‌تایی زوج یال وجود دارد.
با این تعاریف، ثابت می‌کنیم با ۶ راس نمی‌توان ۱۲ یال در گراف داشت و با ۷ راس یک مثال می‌آوریم.
برهان خلف. فرض کنید با ۶ راس بتوان چنین گرافی ساخت. مکمل گراف را در نظر بگیرید. در این گراف در هر سه‌تایی فرد یال داریم (چرا؟).
- اگر دو تا از این یال‌ها در یک راس اشتراک داشته باشند، باید یال سوم با آنها تشکیل یک مثلث دهد که در اینصورت سه راس دیگر صفر یال خواهند داشت و این ممکن نیست.
- اگر هیچ سه یالی در هیچ راسی اشتراک نداشته باشند، از هر یال، یک راس در نظر می‌گیریم و این سه راس در بین خود یالی ندارند که این ممکن نیست.
مثال برای ۷ راس: گرافی کامل دوبخشی با بخش‌های ۳ و ۴ عضوی در نظر بگیرید. این گراف شرایط مسئله را دارد و دارای ۱۲ یال است.
سوال ۳۳
تحقیقات اخیر جمشید نشان می دهد که در سیاره‌ای جدید، ۹ تپلوس با نام‌های $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)$ مشخص گردند بقیه یال‌ها به صورت یکتا تعیین خواهند شد. این یال‌ها نیز هرکدام به صورت مستقل ۲ حالت دارند. در نتیجه تعداد کل حالات برابر ۳۲ خواهد بود.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
