Browse · MathNet
PrintThe South African Mathematical Olympiad Third Round
South Africa counting and probability
Problem
Andile and Zandre play a game on a board. At the beginning, Andile declares some of the squares forbidden, meaning that nothing may be placed on such a square. After that, they take turns to place coins on the board, with Zandre placing the first coin. It is not allowed to place a coin on a forbidden square or in the same row or column where another coin has already been placed. The player who places the last coin wins the game. What is the least number of squares Andile needs to declare as forbidden at the beginning to ensure a win? (Assume that both players use an optimal strategy.)
Solution
The minimum number is . For example, Andile can achieve a win by declaring all squares of the last row forbidden, so that rows remain. After that, there will be exactly moves possible, no matter how the two play, since placing a coin always eliminates exactly one row and one column from further use. This means that Andile gets the last move.
On the other hand, we prove that or fewer forbidden squares are not sufficient, no matter how they are placed. Generally, we show by induction that Zandre has a winning strategy on a board if he gets to place a coin first and no more than squares have been forbidden. This is trivial for : Zandre can simply place a coin on the only square.
For the induction step, consider a board with at most forbidden squares. If there are two forbidden squares in the same row or column somewhere, then Zandre places a coin in this row/column. This is possible since there are fewer forbidden squares than squares in a row or column. If there are at least two forbidden squares but no two of them in the same row or column, Zandre chooses any two of them, then places a coin on the intersection of the row of the first forbidden square and the column of the second forbidden square. This is possible because of the assumption that there are no two forbidden squares in the same row or column. Finally, if there is only one forbidden square, Zandre places a coin anywhere in the same row or column, and if there are no forbidden squares, he just places it on an arbitrary square.
After Andile's move, the rows and columns where Andile and Zandre placed their coins can be removed, since no further coins can be placed there anymore. This leaves us with a board, and by the choice of Zandre's move there are at most forbidden squares on it. So by the induction hypothesis, Zandre has a winning strategy for the remaining position, which completes the proof.
On the other hand, we prove that or fewer forbidden squares are not sufficient, no matter how they are placed. Generally, we show by induction that Zandre has a winning strategy on a board if he gets to place a coin first and no more than squares have been forbidden. This is trivial for : Zandre can simply place a coin on the only square.
For the induction step, consider a board with at most forbidden squares. If there are two forbidden squares in the same row or column somewhere, then Zandre places a coin in this row/column. This is possible since there are fewer forbidden squares than squares in a row or column. If there are at least two forbidden squares but no two of them in the same row or column, Zandre chooses any two of them, then places a coin on the intersection of the row of the first forbidden square and the column of the second forbidden square. This is possible because of the assumption that there are no two forbidden squares in the same row or column. Finally, if there is only one forbidden square, Zandre places a coin anywhere in the same row or column, and if there are no forbidden squares, he just places it on an arbitrary square.
After Andile's move, the rows and columns where Andile and Zandre placed their coins can be removed, since no further coins can be placed there anymore. This leaves us with a board, and by the choice of Zandre's move there are at most forbidden squares on it. So by the induction hypothesis, Zandre has a winning strategy for the remaining position, which completes the proof.
Final answer
2017
Techniques
Games / greedy algorithmsInduction / smoothing