سوال ۳

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

کافی است تعداد روش‌های رنگ‌آمیزی خانه‌های هاشورخورده در شکل زیر را مشخص کرده و حاصل را به توان دو برسانیم، زیرا خانه‌های دیگر به طور مستقل و مشابه رنگ‌آمیزی می‌شوند. $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$ است.