Browse · MathNet
PrintJapan Junior Mathematical Olympiad
Japan counting and probability
Problem
Let be positive integers. square boxes of side length 1 form a grid for a rectangle (or a square if ) of sides and . We want to color each of the boxes by using one of the colors red, blue or black in such a way that all of the following conditions are satisfied: every red box is adjacent to exactly 1 blue box and exactly 1 black box. every blue box is adjacent to exactly 1 black box and exactly 1 red box. * every black box is adjacent to exactly 1 red box and exactly 1 blue box. Here, we say that two different boxes are adjacent to each other if they have a side in common. Answer the following questions in this context: (1) Give an example of coloring satisfying the conditions given above in case . (Give just an example.) (2) Determine all the pairs for which the coloring of boxes satisfying the conditions given above is possible.
Solution
Let us denote by the unit square lying in the -th row and -th column in the given grid. For two unit squares lying in the same row, call the square corresponding to the smaller value of to be lying to the left of the other one, and the one corresponding to the larger value of to be lying to the right of the other one. Similarly, for two squares lying in the same column, call the one corresponding to the smaller value of to be lying above the other, and the one corresponding to the larger value of to be lying below the other.
Let us first consider the case for . Since there is only one square adjacent to the square lying on the top of the column, there can be no coloring of squares satisfying the conditions of the problem. Similarly, the desired coloring cannot exist in the case of .
We will investigate the possibility of a desired coloring in the cases for , , by starting with the square located at the upper left corner.
Without loss of generality, we may assume that we start by coloring the square (1,1) by red, (1,2) by blue and (2,1) by black. Then, the color of (2,2) must be either blue or black, since if (2,2) is colored red, then (1,2) would become adjacent to two red squares, violating the required condition. We suppose that (2,2) is colored by black and continue our investigation. In case blue is chosen for (2,2), we will obtain a coloring satisfying the conditions of the problem if we interchange rows and columns and go through the argument with colors blue and black interchanged.
Now since the color of (2,1) is black, it must become adjacent to a blue colored square. Therefore, we must have the 3rd row, and the square (3,1) must be colored blue. Then, we see that the square (3,2) must be colored red, since if it is colored blue, then the square (2,2) which was colored black would be adjacent to two blue squares violating the requirement of the problem, while if it is colored black, then the square (3,1) which was colored blue would be adjacent to two black squares, again violating the requirement.
Let us next determine the colors of all the squares lying on the top three rows. If there exists the 3rd column, we see that the color of each of the squares (1,3), (2,3), (3,3) must be the same as the color of its left neighbor, since otherwise the requirement of the problem will be violated, as each of the left neighbors is already adjacent to two squares with different colors, different also from its own.
Arguing in the same way, we see that if for some positive integer the -th column exists, then the -th column must exist, and therefore, the number of columns must necessarily be even, and the coloring of top 3 rows in this case must be as in the following diagram.
Based on the results obtained so far, let us try to determine the coloring of the 4-th and further rows starting with the 4-th row and going down. To begin with, we see that if the 4-th row exists, it must have exactly the same coloring pattern as the 3-rd row, since for each square on the 4-th row, the square on the 3-rd row lying immediately above it is already adjacent to each of the two different colors. Thus we have that the color of (4,1) is blue and that of (4,2) is red, but then we see that we need the 5-th row since otherwise the square (4,1) would not be adjacent to a square colored black. But then since any of the squares on the 4-th row is not adjacent to a black square, we see that all the squares on the 5-th row must be colored black.
The square (5,1) colored black, then, is seen not to be adjacent to a red square, so we need the 6-th row, and the square (6,1) must be colored red. As the square (5,2) is not adjacent to a blue square, we see that the square (6,2) has to have the blue color; continuing in this way, we can conclude that the coloring of the 6-th row must be the one obtained by interchanging the blue and red in the 4-th row.
Repeating the same argument we see that if for some positive integer the -th row exists, then both the -th row, and the -th row must exist and the coloring of the -th row must be identical with the -th row, the -th row has all squares colored black and the coloring of the -th row is obtained by interchanging red and blue in -th row. In particular, the number of rows necessary must be a multiple of 3.
Furthermore, we see that for any positive integers any rectangular (or square) grid of squares with the coloring scheme described as above satisfies the conditions of the problem. We also note that interchanging rows and columns (thereby turning the -th row into the -th column, and the -th column into the -th row, we can get from a rectangular grid with a coloring satisfying the conditions of the problem a rectangular grid with a coloring satisfying the conditions of the problem as well.
Thus, we conclude that in order to get a coloring of rectangular grids (with squares) which satisfies the conditions of the problem we have to have to be a multiple of 3 and to be a multiple of 2 (or to be a multiple of 2 and a multiple of 3.) And if these conditions are met, the desired coloring of the grid is obtained by folding the pattern of the upper left corner subgrid over the horizontal line lying in between the 3-rd row and the 4-th row and repeating the folding an appropriate number of times, and then folding the resulting grid over the vertical line lying in between the 2-nd and the 3-rd column appropriate number of times to obtain the coloring of grid which satisfies the conditions of the problem (assuming that .)
(1) From the discussion above, we see that the following arrangement of colors satisfy the condition of the problem.
(Any of the 6 colorings obtained by permuting the three colors in this pattern is also valid.)
(2) All pairs such that is a multiple of 3 and is a multiple of 2, or is a multiple of 2 and is a multiple of 3, i.e., or for positive integers .
Let us first consider the case for . Since there is only one square adjacent to the square lying on the top of the column, there can be no coloring of squares satisfying the conditions of the problem. Similarly, the desired coloring cannot exist in the case of .
We will investigate the possibility of a desired coloring in the cases for , , by starting with the square located at the upper left corner.
Without loss of generality, we may assume that we start by coloring the square (1,1) by red, (1,2) by blue and (2,1) by black. Then, the color of (2,2) must be either blue or black, since if (2,2) is colored red, then (1,2) would become adjacent to two red squares, violating the required condition. We suppose that (2,2) is colored by black and continue our investigation. In case blue is chosen for (2,2), we will obtain a coloring satisfying the conditions of the problem if we interchange rows and columns and go through the argument with colors blue and black interchanged.
Now since the color of (2,1) is black, it must become adjacent to a blue colored square. Therefore, we must have the 3rd row, and the square (3,1) must be colored blue. Then, we see that the square (3,2) must be colored red, since if it is colored blue, then the square (2,2) which was colored black would be adjacent to two blue squares violating the requirement of the problem, while if it is colored black, then the square (3,1) which was colored blue would be adjacent to two black squares, again violating the requirement.
Let us next determine the colors of all the squares lying on the top three rows. If there exists the 3rd column, we see that the color of each of the squares (1,3), (2,3), (3,3) must be the same as the color of its left neighbor, since otherwise the requirement of the problem will be violated, as each of the left neighbors is already adjacent to two squares with different colors, different also from its own.
Arguing in the same way, we see that if for some positive integer the -th column exists, then the -th column must exist, and therefore, the number of columns must necessarily be even, and the coloring of top 3 rows in this case must be as in the following diagram.
Based on the results obtained so far, let us try to determine the coloring of the 4-th and further rows starting with the 4-th row and going down. To begin with, we see that if the 4-th row exists, it must have exactly the same coloring pattern as the 3-rd row, since for each square on the 4-th row, the square on the 3-rd row lying immediately above it is already adjacent to each of the two different colors. Thus we have that the color of (4,1) is blue and that of (4,2) is red, but then we see that we need the 5-th row since otherwise the square (4,1) would not be adjacent to a square colored black. But then since any of the squares on the 4-th row is not adjacent to a black square, we see that all the squares on the 5-th row must be colored black.
The square (5,1) colored black, then, is seen not to be adjacent to a red square, so we need the 6-th row, and the square (6,1) must be colored red. As the square (5,2) is not adjacent to a blue square, we see that the square (6,2) has to have the blue color; continuing in this way, we can conclude that the coloring of the 6-th row must be the one obtained by interchanging the blue and red in the 4-th row.
Repeating the same argument we see that if for some positive integer the -th row exists, then both the -th row, and the -th row must exist and the coloring of the -th row must be identical with the -th row, the -th row has all squares colored black and the coloring of the -th row is obtained by interchanging red and blue in -th row. In particular, the number of rows necessary must be a multiple of 3.
Furthermore, we see that for any positive integers any rectangular (or square) grid of squares with the coloring scheme described as above satisfies the conditions of the problem. We also note that interchanging rows and columns (thereby turning the -th row into the -th column, and the -th column into the -th row, we can get from a rectangular grid with a coloring satisfying the conditions of the problem a rectangular grid with a coloring satisfying the conditions of the problem as well.
Thus, we conclude that in order to get a coloring of rectangular grids (with squares) which satisfies the conditions of the problem we have to have to be a multiple of 3 and to be a multiple of 2 (or to be a multiple of 2 and a multiple of 3.) And if these conditions are met, the desired coloring of the grid is obtained by folding the pattern of the upper left corner subgrid over the horizontal line lying in between the 3-rd row and the 4-th row and repeating the folding an appropriate number of times, and then folding the resulting grid over the vertical line lying in between the 2-nd and the 3-rd column appropriate number of times to obtain the coloring of grid which satisfies the conditions of the problem (assuming that .)
(1) From the discussion above, we see that the following arrangement of colors satisfy the condition of the problem.
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | red | blue | red | blue |
| 2 | black | black | black | black |
| 3 | blue | red | blue | red |
(2) All pairs such that is a multiple of 3 and is a multiple of 2, or is a multiple of 2 and is a multiple of 3, i.e., or for positive integers .
Final answer
(1) Example for 3×4: Row 1: red, blue, red, blue; Row 2: black, black, black, black; Row 3: blue, red, blue, red. (2) All pairs (m, n) with one dimension a multiple of 3 and the other a multiple of 2, i.e., (m, n) = (3s, 2t) or (2t, 3s) for positive integers s, t.
Techniques
Coloring schemes, extremal argumentsInduction / smoothing