MathDB
P_n= number of colorings of 2xn strips ...

Source: Czech and Slovak Olympiad 1989, National Round, Problem 5

September 13, 2024
combinatoricscombinatorial geometryColoring

Problem Statement

Consider a rectangular table 2×n.2 \times n. Let every cell be dyed either by black or white color in a way that no 2×22\times 2 square is completely black. Denote PnP_n the number of such colorings. Prove that the number P1989P_{1989} is divisible by three and find the greatest power of three that divides them.
Back to ProblemsView on AoPS