(solved by Philippe Cloarec). Two players play the following game. They have a rectangular piece of paper with a grid. Taking turns, each player chooses a node from the grid inside the rectangle, or on its left or bottom edge. They shade the squares of the rectangle that are located above and to the right of the chosen node. Then they pass the rectangle to the other player. Each move, each player is required to shade at least one square that has not been shaded before. The player who shades the last square of the rectangle loses. Which of the two players has a winning strategy?
Solution
. For it is the first player who loses on their first move. In all other cases, the first player has a winning strategy. We will demonstrate this without exhibiting the strategy itself.
First, note that this is a finite game and therefore one of the players must have a winning strategy. Suppose it is the second player. We then recommend that the first player hatch just one square: the top right corner of the rectangle. If our assumption is correct, the second player then has a winning move. But in this case, the first player can "retract" their first move and make the winning move instead of the second player. Whatever this move is, the top right corner of the rectangle will be automatically hatched. So the first player can now use the so-called winning strategy of the second player to win. This contradiction shows that it is the first player who has a winning strategy.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.