====== سوال ۳ ======



یک جدول 
$4 \times 4$
داریم و می‌خواهیم هر یک از خانه‌های آن را با سیاه یا سفید رنگ کنیم. یک خانه را 
**امن**
گوییم، اگر در ستون اوّل، ستون آخر و سطر پایین نباشد و هم‌چنین هر سه خانه‌ی مجاور چپ، راست و پایین آن سیاه باشند. به چند طریق می‌توان خانه‌های  جدول را رنگ‌آمیزی کرد، طوری که خانه‌ی امن نداشته باشیم؟

  - $31684$
  - $178$
  - $19321$
  - $22500$
  - $2^{12}$







<پاسخ>
گزینه (۱) درست است.

کافی است تعداد روش‌های رنگ‌آمیزی خانه‌های هاشورخورده در شکل زیر را مشخص کرده و حاصل را به توان دو برسانیم، زیرا خانه‌های دیگر به طور 
__مستقل و مشابه__
رنگ‌آمیزی می‌شوند.
{{ :سوالات_المپیاد:مرحله‌ی_دوم:دوره‌ی_۲۷:p3.png?200 |}}
$a_{n}$
را تعداد روش‌های رنگ‌آمیزی خانه‌های هاشورخورده از سطر یکم تا سطر $n$ ام (از پایین) می‌نامیم. به این ترتیب داریم
$a_0 = 1$، $a_1 = 4$
و به ازای هر 
$n \ge 2$:
$$a_n = 3a_{n-1} + 2a_{n-2}$$
پس مقدار $a_4$ برابر
$178$
و پاسخ برابر
$a_4^2 = 31684$
است.


</پاسخ>
  * [[سوال ۲|سوال قبل]]
  * [[سوال ۴|سوال بعد]]