In a $9\times9$ board, the squares are labeled from 11 to 99, with the first digit indicating the row and the second digit indicating the column. One would like to paint the squares in black or white in a way that each black square is adjacent to at most one other black square and each white square is adjacent to at most one other white square. Two squares are adjacent if they share a common side. How many ways are there to paint the board such that the squares $44$ and $49$ are both black?
Problem
Source: Lusophon Mathematical Olympiad 2024 Day 2 Problem 5
Tags: combinatorics
Davdav1232
26.07.2024 22:18
I am pretty sure the answer is 29. The main idea is: because of the restriction, each color comes in pairs of adjacent blocks, or as a single block, and in no other shapes. This means that if we have 2 black squares in a row, horizontally, we also have 2 white squares underneath this shape, and above. This implies that the rows or the columns are 2 periodic. Assuming this is not a chess coloring (it doesn't work), if the coloring is 2 periodic in the columns that means that 44 and 49 are different colors, contradiction. Now we need to check the option of the rows being 2 periodic, which means we only have to check one row, the 4th one. I didn't see a nice way to count it except doing some stuff with fibonacci that actually isn't that nice so I won't include the final counting.