ระบายสีตาราง 7x7

[ฟินิกซ์เหินฟ้า]

โธมัส มุลเลอร์ต้องการระบายสีตารางขนาด $7 \times 7$ ด้วยสีขาวกับดำ โดยห้ามมีสามช่องติดกันใดๆที่ถูกระบายด้วยสีเดียว มุลเลอร์จะทำได้กี่วิธี

[MINGA]

ถ้าหากในการระบายสี มีสีดำหรือสีขาวติดกันในแนวนอน จะบังคับให้ทั้งคอลัมน์ต้องระบายด้วยสองสีติดกันในแนวนอนตามรูป

เช่นเดียวกัน ถ้าการระบายสีเหมือนกันติดกันในแนวตั้ง จะบังคับให้ทั้งแถวต้องระบายด้วยสองสีติดกันในแนวตั้งด้วย(ตามรูป)

ดังนั้น จำนวนวิธีการระบายสีทั้งหมด = การระบายโดยไม่มีสีเดียวกันติดกัน + มีสีเดียวกันติดกันแนวตั้ง + มีสีเดียวกันติดกันแนวนอน

จำนวนวิธีที่ไม่สีเดียวกันติดกันเลย = 2 (= ระบายแบบตารางหมากรุก)

จำนวนวิธีที่มีสีเดียวกันติดกันแนวตั้ง = จำนวนวิธีที่มีสีเดียวกันติดกันแนวนอน

จำนวนวิธีที่มีสีเดียวกันติดกันแนวนอน = จำนวนวิธีการระบายตาราง 1 x 7 = 2 x ( สีเดียวกันติดกันหนึ่งคู่ + สองคู่ + สามคู่ ) = $ 2\left( {6 \choose 1} + {5 \choose 2} + {4\choose 3} \right) = 40$

ดั้งนั้น จำนวนวิธีทั้งหมด = $ 2 + 2\times 40 = 82$