Maths Olympiad Prep

Library / /259 of 348

Combinatorics Difficulty 5.0 AIME, harder Find the answer

Each cell of a 2×52 \times 5 grid of unit squares is to be colored white or black. Compute the number of such colorings for which no 2×22 \times 2 square is a single color.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let ana_{n} denote the number of ways to color a 2×n2 \times n grid subject only to the given constraint, and bnb_{n} denote the number of ways to color a 2×n2 \times n grid subject to the given constraint, but with the added restriction that the first column cannot be colored black-black. Consider the first column of a 2×n2 \times n grid that is not subject to the additional constraint. It can be colored black-white or white-black, in which case the leftmost 2×22 \times 2 square is guaranteed not to be monochromatic, and so the remaining 2×(n1)2 \times(n-1) subgrid can be colored in an1a_{n-1} ways. Otherwise, it is colored white-white or black-black; WLOG, assume that it's colored black-black. Then the remaining 2×(n1)2 \times(n-1) subgrid is subject to both constraints, so there are bn1b_{n-1} ways to color the remaining subgrid. Hence an=2an1+2bn1a_{n}=2 a_{n-1}+2 b_{n-1}. Now consider the first column of a 2×n2 \times n grid that is subject to the additional constraint. The first column cannot be colored black-black, and if it is colored white-black or black-white, there are an1a_{n-1} ways to color the remaining subgrid by similar logic to the previous case. If it is colored white-white, then there are bn1b_{n-1} ways to color the remaining subgrid, again by similar logic to the previous case. Hence bn=2an1+bn1b_{n}=2 a_{n-1}+b_{n-1}. Therefore, we have bn=2an1+12(an2an1)b_{n}=2 a_{n-1}+\frac{1}{2}\left(a_{n}-2 a_{n-1}\right), and so an=2an1+2bn1=2an1+2(2an2+a_{n}=2 a_{n-1}+2 b_{n-1}=2 a_{n-1}+2\left(2 a_{n-2}+\right. 12(an12an2))=3an1+2an2\left.\frac{1}{2}\left(a_{n-1}-2 a_{n-2}\right)\right)=3 a_{n-1}+2 a_{n-2}. Finally, we have a0=1a_{0}=1 (as the only possibility is to, well, do nothing) and a1=4a_{1}=4 (as any 2×12 \times 1 coloring is admissible), so a2=14,a3=50,a4=178,a5=634a_{2}=14, a_{3}=50, a_{4}=178, a_{5}=634.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.