Browse · MathNet
PrintThe 4th Japanese Junior Mathematical Olympiad
Japan counting and probability
Problem
A 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.
(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 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 ways to color the corners. Therefore there are 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 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 ways.
(ii) Case we use exactly 2 colors. (a) If exactly three edges have the same color, there are ways. (b) If two opposing edges have the same color and the rest have the other color, there are ways. (c) If two non-opposing edges have the same color and the rest have the other color, there are ways.
(iii) Case we use 3 colors. (a) If two opposing edges have the same color and the rest have different colors, there are ways. (b) If two non-opposing edges have the same color and the rest have different colors, there are ways.
Consequently, there are ways in total.
(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 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 ways to color the corners. Therefore there are 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 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 ways.
(ii) Case we use exactly 2 colors. (a) If exactly three edges have the same color, there are ways. (b) If two opposing edges have the same color and the rest have the other color, there are ways. (c) If two non-opposing edges have the same color and the rest have the other color, there are ways.
(iii) Case we use 3 colors. (a) If two opposing edges have the same color and the rest have different colors, there are ways. (b) If two non-opposing edges have the same color and the rest have different colors, there are ways.
Consequently, there are ways in total.
Final answer
(1) 246; (2) 9612
Techniques
Coloring schemes, extremal arguments