Browse · MathNet
PrintThe 16th Japanese Mathematical Olympiad - The First Round
Japan counting and probability
Problem
A grid is given. We color each square by red or blue so that no red square nor blue square appears. How many such colorings are there? 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. Call the edges , , and clockwise. We divide the cases by how many edges are colored red. Note that any square must include the center.
If there are no red edge, or if just one was red, or if two opposing edges were colored red, then however we color the 4 corners, no red square appears. So we can color each of these 4 squares in arbitrary color. On the second case, we have 4 ways each to choose which edge to be colored red. On the third case, we have 2 ways. Hence this case has ways.
If two non-opposing edges were colored red, one corner which is between two red edges must be colored blue, and the other squares can be colored arbitrarily. So this case has ways.
If there are exactly three red edges, there are exactly 2 corners which are between two red edges and they must be colored blue. Others can be arbitrary color. So this case has ways.
If all the four edges are colored red, all the corners must be colored blue. There is only 1 way of coloring.
There are the same number of ways of coloring if the center square was colored blue. So we have ways of coloring.
If there are no red edge, or if just one was red, or if two opposing edges were colored red, then however we color the 4 corners, no red square appears. So we can color each of these 4 squares in arbitrary color. On the second case, we have 4 ways each to choose which edge to be colored red. On the third case, we have 2 ways. Hence this case has ways.
If two non-opposing edges were colored red, one corner which is between two red edges must be colored blue, and the other squares can be colored arbitrarily. So this case has ways.
If there are exactly three red edges, there are exactly 2 corners which are between two red edges and they must be colored blue. Others can be arbitrary color. So this case has ways.
If all the four edges are colored red, all the corners must be colored blue. There is only 1 way of coloring.
There are the same number of ways of coloring if the center square was colored blue. So we have ways of coloring.
Final answer
322
Techniques
Enumeration with symmetryColoring schemes, extremal arguments