Processing math: 100%

سوال ۳

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

  1. 31684
  2. 178
  3. 19321
  4. 22500
  5. 212

پاسخ

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

کافی است تعداد روش‌های رنگ‌آمیزی خانه‌های هاشورخورده در شکل زیر را مشخص کرده و حاصل را به توان دو برسانیم، زیرا خانه‌های دیگر به طور مستقل و مشابه رنگ‌آمیزی می‌شوند. an را تعداد روش‌های رنگ‌آمیزی خانه‌های هاشورخورده از سطر یکم تا سطر n ام (از پایین) می‌نامیم. به این ترتیب داریم a0=1، a1=4 و به ازای هر n2: an=3an1+2an2 پس مقدار a4 برابر 178 و پاسخ برابر a24=31684 است.