المپدیا

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

ابزار کاربر

ابزار سایت


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

سؤال ۱۳

به چند طریق می‌توان خانه‌های یک جدول $ ۱۰× ۳ $ (۱۰ سطر و ۳ ستون) را با دورنگ سیاه‌و سفید رنگ کرد، به‌طوری‌که:

• رنگ خانه‌ها نسبت به ستونِ وسط متقارن باشد.

• از هر دو سطرِ متوالی حداقل یک‌ خانه سیاه شده باشد.

• هیچ دوخانه‌ی سیاه مجاور هم نباشند. دوخانه مجاورند اگر یک ضلع مشترک داشته باشند.

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

پاسخ

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

هر سطر به یکی از ۳ شکل ٬ و یا می‌تواند باشد به شرطی که اگر سطر $i$ام به یکی از آن سه شکل بود سطر $(i+1)$ام نیز نمی‌تواند به همان شکل باشد٬ بنابراین سطر اول ۳حالت و مابقی سطرها وابسته به نوع شکل سطر قبل از خود٬ به یکی از دو شکل دیگر می‌تواند باشد٬ بنابراین طبق اصل ضرب جواب مورد نظر $3\times2^9$ یعنی ۱۵۳۶ می‌باشد


ابزار صفحه