Cayley 2016 Q5
5. Dean wishes to place the positive integers 1, 2, 3, …, 9 in the cells of a \(3 \times 3\) square grid so that:
| (i) | there is exactly one number in each cell; |
| (ii) | the product of the numbers in each row is a multiple of four; |
| (iii) | the product of the numbers in each column is a multiple of four. |
Is Dean's task possible? Prove that your answer is correct.
Cayley Olympiad 2016, Question 5. © UK Mathematics Trust. Original paper on ukmt.org.uk
We claim that Dean's task is impossible, and will prove our claim by contradiction.
Suppose Dean has placed the integers according to the given rules.
Now only one row contains 4, and only one row contains 8. But there are three rows, so there is at least one row \(R\) which contains neither 4 nor 8. From rule (ii), the product of the numbers in \(R\) is a multiple of 4 and hence \(R\) contains both 2 and 6.
In a similar way, there is at least one column \(C\) that contains neither 4 nor 8. From rule (iii), the product of the numbers in \(C\) is a multiple of 4 and hence \(C\) contains both 2 and 6.
As a result, both 2 and 6 are in the same row, and in the same column, which contradicts rule (i).
Therefore Dean's task is not possible.
Solution © UK Mathematics Trust, from the Cayley Olympiad 2016 solutions.