Maths Olympiad Prep

Track / Stage 5 / 308 of 400 #1388 of 2444

Problem 1388

AIME late
Combinatorics Difficulty 5.7 Find the answer AIME II · United States

Four unit squares form a 2×22 \times 2 grid. Each of the 1212 unit line segments forming the sides of the squares is colored either red or blue in such a way that each unit square has 22 red sides and 22 blue sides. One example is shown below (red is solid, blue is dashed). Find the number of such colorings.
Figure 1

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

Next problem →

Official solution

Call the 88 unit segments along the outside of the figure outer edges, and call the remaining 44 unit segments inner edges. The count can be organized by the number of red inner edges.
* If all 44 of the inner edges are red, then in order for each square to be bounded by 22 red segments and 22 blue segments, all the outer edges must be blue. This gives 11 coloring.

* If 33 of the inner edges are red, then there are 44 ways to choose which inner edge is blue, there is only 11 way to color the outer edges of the 22 squares not bounded by the blue inner edge, and there are 22 ways to color the outer edges of each of the 22 squares that are bounded by the blue inner edge. This gives 422=164 \cdot 2 \cdot 2 = 16 colorings.

* If 22 of the inner edges are red and these edges form a 9090^\circ angle (as in the figure), then there are 44 ways to choose these 22 red inner edges, 22 ways to color the outer edges of 22 of the squares, but only 11 way to color the outer edges of the other 22 squares. Again this gives 422=164 \cdot 2 \cdot 2 = 16 colorings.

* If 22 of the inner edges are red and these edges are collinear, then there are 22 ways to choose these 22 red inner edges and 22 ways to color the outer edges of each of the 44 squares. This gives 224=322 \cdot 2^4 = 32 colorings.

By symmetry, the number of colorings with 11 or 00 red inner edges is the same as the number of colorings with 33 or 44 red inner edges, respectively. The final count is therefore 1+16+16+32+16+1=821 + 16 + 16 + 32 + 16 + 1 = 82.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.