Competition problem — Combinatorics

Combinatorics Difficulty 4.1 AIME Prove it Japan

A $3 \times 3$ grid is given. You shall color each square with one of the given colors. However, you may not color two squares sharing an edge with the same color. How many such colorings are there if you can use

(1) three colors (say red, blue and green)?

(2) four colors (say red, blue, green and yellow)?

It is not necessary to use all the colors. We consider two colorings different even if they correspond by rotation and/or reversal.

Solution

We call the squares corners, edges or the center, according to their position. We first consider the case that the center is colored red.

(1) The edges must be colored into blue or yellow. There are 2 ways to color a square on the corner if the two squares next to it have the same color, and there are 1 way if otherwise. Split the cases by how the edges are colored.

(i) If all 4 edges have the same color, there are $2 \times 2^4 = 32$ ways.

(ii) If exactly 3 edges have the same color, there are 4 ways to choose the edge with the different color, 2 ways to choose its color, and $2^2$ ways to color the corners. Therefore there are $2 \times 4 \times 2^2 = 32$ ways.

(iii) If two opposing edges have the same color and the rest have the other color, there are 2 ways.

(iv) If two non-opposing edges have the same color and the rest have the other color, there are $4 \times 2^2 = 16$ ways.

(2) The edges must be colored into blue, yellow or green. There are 3 ways to color a square on the corner if the two squares next to it have the same color, and there are 2 ways if otherwise. Split the cases by how the edges are colored.

(i) Case we use single color on the edges.
(a) If all four edges have the same color, there are $3 \times 3^4 = 243$ ways.

(ii) Case we use exactly 2 colors.
(a) If exactly three edges have the same color, there are $3 \times 2 \times 4 \times 3^2 \times 2^2 = 864$ ways.
(b) If two opposing edges have the same color and the rest have the other color, there are $3 \times 2 \times 2^4 = 96$ ways.
(c) If two non-opposing edges have the same color and the rest have the other color, there are $3 \times 4 \times 2^2 \times 3^2 = 432$ ways.

(iii) Case we use 3 colors.
(a) If two opposing edges have the same color and the rest have different colors, there are $3 \times 2 \times 2 \times 2^4 = 192$ ways.
(b) If two non-opposing edges have the same color and the rest have different colors, there are $3 \times 4 \times 2 \times 3 \times 2^3 = 576$ ways.

Consequently, there are $2403 \times 4 = 9612$ ways in total.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.