المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۵

به چند طریق می‌توان خانه‌های یک جدول $۳\times ۵$ را با دو رنگ سیاه و سفید رنگ‌آمیزی کرد به نحوی که شکل سمت چپ در آن یافت نشود؟ این شکل شامل یک خانه‌ي سیاه و هشت خانه‌ی سفید مجاور آن است.

  1. ۳۲۵۷۷
  2. ۳۲۶۴۱
  3. ۳۲۷۶۹
  4. ۳۲۷۶۸
  5. ۳۲۵۷۶

پاسخ

گزینه‌ی (۱) درست است.

تعداد جدول‌هایی که شامل آن شکل هستند را می‌شماریم. این جدول‌ها یکی از سه حالت زیر را دارند:

تعداد حالات هر کدام $2^6$ است، ولی تنها در یک حالت وضعیت اول وسوم یکسان خواهند شد. در نتیجه تعداد کل حالات نامطلوب برابر است با: $3×2^6-1$. پس جواب مسئله برابر $2^{15}-(3×2^6-1)$ می‌باشد که ۳۲۵۷۷ می‌شود.


ابزار صفحه