MOG 2016 Q3
Punam puts counters onto some of the cells of a \(5 \times 5\) board. She can put more than one counter on each cell, and she can leave some cells empty. She tells Quinn how many counters there are in each row and column. These ten numbers are all different.
Can Quinn always work out which cells, if any, are empty?
Mathematical Olympiad for Girls 2016, Question 3. © UK Mathematics Trust. Original paper on ukmt.org.uk
Answer: No
Commentary
It is usually a good idea to start by trying to produce some examples of arrangements of counters that satisfy the given condition.
You then need to decide what you are trying to prove, drawing on your experience from experimenting with some examples of ways of arranging the counters.
If you think that Quinn can always work out which cells are empty then you need to show that this is the case for all possible arrangements for which the ten row and column totals are all different.
If you think that Quinn cannot identify the empty cells, then you need to find an example of two different arrangements which have the same row and column totals, but the empty cells in different places.
No, it is not always possible for Quinn to identify the empty cells. Consider two arrangements \(X\), \(Y\) of Punam’s counters that are the same except in the top left \(2 \times 2\) square, where, say, \(X\) has \(\begin{array}{|c|c|}\hline 0&1\\\hline 1&0\\\hline\end{array}\) while \(Y\) has \(\begin{array}{|c|c|}\hline 1&0\\\hline 0&1\\\hline\end{array}\).
For example, \(X\) and \(Y\) could be as shown in the figures below.
| 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 | 3 |
| 0 | 3 | 1 | 0 | 0 |
| 9 | 8 | 7 | 6 | 5 |
| 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 | 3 |
| 0 | 3 | 1 | 0 | 0 |
| 9 | 8 | 7 | 6 | 5 |
The row totals in these examples are 1, 2, 3, 4, 35 and the column totals are 10, 12, 9, 6, 8, all different.
Since Quinn knows only the total numbers of counters in each row and column, she could not distinguish \(X\) from \(Y\), and therefore she cannot work out which cells are empty.
Note
If the problem is modified so that Punam can put at most one counter on each cell, with the condition that all the row totals are different and all the column totals are different, then Quinn can use the row and column totals to work out which cells are empty. Can you prove this?
Solution © UK Mathematics Trust, from the MOG 2016 solutions.