Skip to main content
OlympiadHQ

Browse · MathNet

Print

XXVII Olimpiada Matemática Rioplatense

Argentina counting and probability

Problem

The faces of a cube of size are painted in black, grey and white, two faces in each color, so that opposite faces have the same color. We have a squared board divided into cells of .

Ana and Beatriz play the following game. First, Ana puts the cube on a cell of the board so that the face of the cube that is in contact with the board coincides with that cell. Then, Beatriz and Ana, alternately, flip the cube, putting it on an adjacent cell, as shown in the picture:
problem


The cube is allowed to come back to a cell only if the color of the face in contact with the cell is different from the colors of the faces that were in contact with the cell previously. Thus, the cube may visit a cell at most three times; one with a black face, another one with a grey face, and another one with a white face.

The player that in her turn is not able to make a valid move loses the game. Determine which player has a winning strategy.

problem


problem


problem


problem


problem


problem
Solution
Beatriz has a winning strategy. In order to win, Beatriz has to split the board into horizontal dominoes and, whenever Ana occupies one cell of a domino, Beatriz in its turn must occupy the other cell of the same domino. To see that this strategy works, we may ensure that if and are the two cells corresponding of the same domino and Ana visits the cell with a color that has not been previously used in , then Beatriz may visit the cell with a color that has not been previously used in (and conversely).

For simplicity, we will denote the black color by 1, the grey color by 2 and the white color by 3. We may represent the colors of the faces of the cube as in Figure 1: the face that is in contact with the cell is , the lateral faces to the left and to the right are , and the lateral faces at the front and the back are . For instance, the cube in Figure 2 is represented as in Figure 3. Figure 1 Figure 2 Figure 3

Now, consider the orientation of the cube, which is the order (clockwise or counter-clockwise) in which the colors 1, 2, 3 appear in the upper-right corner of its representation. For example, the cube in Figure 2 has the clockwise orientation, since the numbers 1, 2, 3 appear in the clockwise direction in Figure 3.

Note that, when making a move, the orientation of the cube changes; then, when the cube comes back to a cell, its orientation is the same as the orientation in its previous visit to that cell (since an even number of moves is necessary for the cube to come back to a cell). Consider now a horizontal domino with two cells and assume, without loss of generality, that the cube has the clockwise orientation in the cell (the other case is similar). Hence, it will always have the clockwise orientation in the cell and the counter-clockwise orientation in the cell . Therefore, if Ana puts the cube in one of these cells and Beatriz were not able to put it in the other one without color repetition, then Ana should have repeated color in her turn, since is visited with color 1 if and only if is visited with color 2, is visited with color 2 if and only if is visited with color 3, and is visited with color 3 if and only if is visited with color 1.



We conclude that, if Ana can make a valid move, then Beatriz also can in her turn, so Beatriz does not lose the game. Since the game eventually ends, Beatriz wins by following the described strategy.
Final answer
Beatriz

Techniques

Games / greedy algorithmsInvariants / monovariants