Maths Olympiad Prep

Library / /7 of 9

Combinatorics Difficulty 7.0 National Olympiad, round 2 Prove it Switzerland

Problem:

Let (m,n)(m, n) be a pair of positive integers. Julia has carefully planted mm rows of nn dandelions in an m×nm \times n array in her back garden. Now, Jana and Viviane decide to play a game with a lawnmower they just found. Taking alternating turns and starting with Jana, they can mow down all the dandelions in a straight horizontal or vertical line (and they must mow down at least one dandelion!). The winner is the player who mows down the final dandelion. Determine all pairs (m,n)(m, n) for which Jana has a winning strategy.

Solution

Solution:

First we make two general observations about the problem. Firstly, since the game always finishes in a finite number of moves there is always a winner and consequently a player who has a winning strategy at the start. Secondly, when a player mows down a row or a column, it does not matter which row or column is chosen (as long as it is still a row respectively a column). The remaining dandelions are affected by further moves in the exact same manner no matter which rows or columns were previously mowed down.

Due to the second observation, each move results in a situation which can be viewed as the start of a game, but this time the other player begins and either mm or nn is decreased by 11. Therefore we can deduce which player has a winning strategy by considering the smaller array. This suggests an inductive approach to the problem.

If m=1m=1 or n=1n=1, then Jana can clearly win the game with a single move. Now we prove the answer above using induction over m+nm+n, so suppose that m+nm+n is odd and m,n>1m, n>1. The case m+n=1m+n=1 is impossible and m+n=3m+n=3 has already been taken care of. If m+n5m+n \geq 5, then one of m,nm, n is at least 33 and it is possible for Jana to mow down a line such that at least 22 rows and 22 columns are left. Then Viviane cannot win in her next move and afterwards the sum of the number of rows and columns will be odd again. By induction, we know that Jana will have a winning strategy for the remainder of the game.

If m+nm+n is even and m,n>1m, n>1, then Jana's first move will result in a configuration for which Viviane 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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.