به چند طریق میتوان خانههای یک جدول $ ۱۰× ۳ $ (۱۰ سطر و ۳ ستون) را با دورنگ سیاهو سفید رنگ کرد، بهطوریکه:
• رنگ خانهها نسبت به ستونِ وسط متقارن باشد.
• از هر دو سطرِ متوالی حداقل یک خانه سیاه شده باشد.
• هیچ دوخانهی سیاه مجاور هم نباشند. دوخانه مجاورند اگر یک ضلع مشترک داشته باشند.
پاسخ
گزینه (۴) درست است.
هر سطر به یکی از ۳ شکل ٬ و یا میتواند باشد به شرطی که اگر سطر $i$ام به یکی از آن سه شکل بود سطر $(i+1)$ام نیز نمیتواند به همان شکل باشد٬ بنابراین سطر اول ۳حالت و مابقی سطرها وابسته به نوع شکل سطر قبل از خود٬ به یکی از دو شکل دیگر میتواند باشد٬ بنابراین طبق اصل ضرب جواب مورد نظر $3\times2^9$ یعنی ۱۵۳۶ میباشد