المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲

یک جدول $۲\times۲$ مانند شکل روبه‌رو داده شده است. این جدول با استفاده از ۱۲ چوب کبریت به طول واحد ساخته شده است. به چند طریق می‌توان ۲ چوب کبریت را رنگ کرد٬ به طوری که چوب کبریت‌های رنگ شده باهم برخورد نداشته باشند؟ دو چوب کبریت با هم برخورد دارند اگر رأس مشترک داشته باشند.

  1. ۴۸
  2. ۵۰
  3. ۵۲
  4. ۵۴
  5. ۶۴

پاسخ

پاسخ درست در میان گزینه‌ها نیست.

برای هرکدام از چوب‌کبریت‌ها فرض می‌کنیم که رنگ شده باشد و تعداد حالاتی را می‌توان چوب‌کبریت دوم را انتخاب کرد به‌دست می‌آوریم. در نهایت چون هر حالت را دو بار شمردیم جواب را بر دو تقسیم می‌کنیم.

برای هر ۴ چوب کبریت وسطی ۶ حالت انتخاب و برای هر ۸ چوب کبریت محیطی ۸ حالت داریم که در کل می‌شود ۲۴+۶۴. پس جواب مسئله برابر نصف این عدد یعنی ۴۴ خواهد بود که در گزینه‌ها نیست.


ابزار صفحه