المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۶:سوال ۲۲

سوال ۲۲

شکل مقابل از تعدادی دایره و میله در صفحه ساخته شده است. می‌خواهیم هر یک از دایره‌های این شکل را با یکی از سه رنگ قرمز، آبی و سبز رنگ کنیم، طوری که هر دو دایره‌ای که با میله به هم وصل هستند، ناهم‌رنگ باشند. به چند طریق این کار ممکن است؟ دو روش رنگ‌آمیزی را که با دوران شکل در صفحه به هم تبدیل می‌شوند، یکسان در نظر می‌گیریم.

  1. ۶
  2. ۱۲
  3. ۲۴
  4. ۶۰
  5. ۱۲۰

پاسخ

گزینه‌ی ۳ درست است.

دور پنج‌تایی وسط را در نظر بگیرید. اگر از یکی از رنگ‌ها سه توپ در این دور داشته باشیم، طبق اصل لانه کبوتری دو تا از آن‌ها مجاور خواهند شد که امکان ندارد. پس تنها حالت برای دور پنج‌تایی وسط این است که از دو رنگ، هر کدام دو توپ و از رنگ دیگر یک توپ داشته باشیم. بدون از دست دادن کلیت مسئله (به ۳ حالت) فرض کنید از رنگ قرمز یک توپ در دور پنج‌تایی وسط داشته باشیم. یکی از توپ‌های این دور را به ۱ حالت قرمز کرده و شیء را طوری می‌چرخانیم که توپ قرمز بالا قرار بگیرد. چهار توپ دیگر این دور باید یک در میان با آبی و سبز رنگ شوند که ۲ حالت دارد. پس از رنگ کردن این دور، شیء به شکلی مانند شکل مقابل در می‌آید.

رنگ توپ بالایی ۲ حالت دارد. فرض کنید آبی باشد. در این صورت با حرکت در جهت ساعت‌گرد از این توپ، رنگ دو توپ بعدی به طور یکتا تعیین می‌شود و شیء به شکل مقابل در می‌آید. دو توپ باقی‌مانده تنها با توپ‌های آبی مجاور هستند. یکی این دو توپ باید قرمز و دیگری سبز باشد که ۲ حالت دارد.

پس کل کار به $3 \times 2 \times 2 \times 2 = 24$ حالت قابل انجام است.


ابزار صفحه