Four unit squares form a grid. Each of the unit line segments forming the sides of the squares is colored either red or blue in such a way that each unit square has red sides and blue sides. One example is shown below (red is solid, blue is dashed). Find the number of such colorings.
Problem 1388
Official solution
Call the unit segments along the outside of the figure outer edges, and call the remaining unit segments inner edges. The count can be organized by the number of red inner edges.
* If all of the inner edges are red, then in order for each square to be bounded by red segments and blue segments, all the outer edges must be blue. This gives coloring.
* If of the inner edges are red, then there are ways to choose which inner edge is blue, there is only way to color the outer edges of the squares not bounded by the blue inner edge, and there are ways to color the outer edges of each of the squares that are bounded by the blue inner edge. This gives colorings.
* If of the inner edges are red and these edges form a angle (as in the figure), then there are ways to choose these red inner edges, ways to color the outer edges of of the squares, but only way to color the outer edges of the other squares. Again this gives colorings.
* If of the inner edges are red and these edges are collinear, then there are ways to choose these red inner edges and ways to color the outer edges of each of the squares. This gives colorings.
By symmetry, the number of colorings with or red inner edges is the same as the number of colorings with or red inner edges, respectively. The final count is therefore .