المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۸

مرتضی یک جدول $8 \times 8$ را با دومینو (کاشی‌های $1 \times 2$) پوشانده و از هر دومینو یک خانه را سیاه و یک خانه را سفید کرده است. گوییم دو خانه‌ی سیاه $A$ و $B$ دوست هستند، هر گاه بتوان از $A$ شروع کرده، در هر مرحله به یک خانه‌ی مجاور (مشترک در ضلع) سیاه رفته و پس از تعدادی مرحله به $B$ رسید. مجموعه‌ای از خانه‌های سیاه را دیدنی گوییم، هر گاه هر دو خانه‌ی مجموعه، دوست باشند. بیشینه‌ی ممکن تعداد خانه‌ها‌ی یک مجموعه‌ی دیدنی چیست؟

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

راهنمایی

دومینو‌ها را به جهت $2 \times 1$ طوری در سطر اول و دوم قرار دهید که خانه‌ی سیاه آن‌ها در سطر دوم قرار گیرد.

راهنمایی

خانه‌های دیگر را به شکل ستونی و با دومینو‌های $1 \times 2$ پر کنید.

پاسخ

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

واضح است که جواب از ۳۲ بیش‌تر نیست، زیرا ۳۲ دومینو داریم. جدول زیر نیز مثالی برای یک مجموعه‌ی دیدنی با ۳۲ خانه است )جهت وضوح، به جای سیاه از قرمز استفاده کرده‌ایم):


ابزار صفحه