Browse · MathNet
PrintJunior Balkan Mathematical Olympiad
North Macedonia counting and probability
Problem
A board, consisting of 25 unit squares, a positive integer and an unlimited supply of -shapes are given. Two players, and , play the following game: starting with they alternatively mark a previously unmarked unit square until they mark a total of unit squares.
We say that a placement of -shapes on unmarked unit squares is called good if the -shapes do not overlap and each of them covers exactly three unmarked unit squares of the board. wins if every good placement of -shapes leaves uncovered at least three unmarked unit squares. Determine the minimum value of for which has a winning strategy.
We say that a placement of -shapes on unmarked unit squares is called good if the -shapes do not overlap and each of them covers exactly three unmarked unit squares of the board. wins if every good placement of -shapes leaves uncovered at least three unmarked unit squares. Determine the minimum value of for which has a winning strategy.
Solution
If , player marks the upper left corner of the square and then fills it as follows.
If , player marks the upper left corner of the square. Whatever square player marks, then player can fill in the square in exactly the same pattern as above except that he doesn't put the trimino which covers the marked square of . Player wins because he has left only two unmarked squares uncovered.
For , player wins by following the same strategy. When he has to mark a square for the second time, he marks any yet unmarked square of the triomino that covers the marked square of .
Let us now show that for player winning strategy. Since there will be 21 unmarked squares, player will need to cover all of them with seven -shaped triominoes. We can assume that in his first move, player does not mark any square in the bottom two rows of the chessboard (otherwise just rotate the chessboard). In his first move player marks the square labeled 1 in the following figure.
If player in his next move marks the squares 2 then player marks the square labeled 5. Player wins as the square labeled 3 is left unmarked but cannot be covered with an -shaped triomino.
Finally, if player in his next move marks one of the squares labeled 3 or 4, player marks the other of these two squares. Player wins as the square labeled 2 is left unmarked but cannot be covered with an -shaped triomino.
Since we have covered all possible cases, player wins when .
If , player marks the upper left corner of the square. Whatever square player marks, then player can fill in the square in exactly the same pattern as above except that he doesn't put the trimino which covers the marked square of . Player wins because he has left only two unmarked squares uncovered.
For , player wins by following the same strategy. When he has to mark a square for the second time, he marks any yet unmarked square of the triomino that covers the marked square of .
Let us now show that for player winning strategy. Since there will be 21 unmarked squares, player will need to cover all of them with seven -shaped triominoes. We can assume that in his first move, player does not mark any square in the bottom two rows of the chessboard (otherwise just rotate the chessboard). In his first move player marks the square labeled 1 in the following figure.
If player in his next move marks the squares 2 then player marks the square labeled 5. Player wins as the square labeled 3 is left unmarked but cannot be covered with an -shaped triomino.
Finally, if player in his next move marks one of the squares labeled 3 or 4, player marks the other of these two squares. Player wins as the square labeled 2 is left unmarked but cannot be covered with an -shaped triomino.
Since we have covered all possible cases, player wins when .
Final answer
4
Techniques
Games / greedy algorithmsInvariants / monovariants