Maths Olympiad Prep

Library / /66 of 74

, 2016

Combinatorics Difficulty 6.5 National Olympiad Prove it Slovenia

Let n3n \ge 3 be a positive integer. We wish to inscribe into each square of the n×nn \times n array one of the numbers 11, 22 or 33, so that any three squares which can be covered using the following shape [ ] [ ] [ ] (which can also be rotated) will contain three different numbers. In how many different ways can this be done?

Solution

First notice that choosing two of the numbers in adjacent squares completely determines the remaining numbers in that row or column.
If we can inscribe the numbers as required then any permutation of the labels 11, 22 and 33 will also give us a correct solution. We can put the numbers 11, 22 and 33 in 66 different orders, namely (1,2,3)(1, 2, 3), (1,3,2)(1, 3, 2), (2,1,3)(2, 1, 3), (2,3,1)(2, 3, 1), (3,1,2)(3, 1, 2) and (3,2,1)(3, 2, 1).
So, we have to count the arrays which contain 11, 22, 33, in this order, in the first three squares of the first row, and multiply the result by 66.
Placing 11, 22 and 33 in the first three squares of the first row gives us two possibilities for the first square of the second row, 22 or 33. In both cases the remainder of the upper left 3×33 \times 3 square is then uniquely determined and is

123
231
312
123
312
231

or
Using the same argument we can show that the remainder of the array is now also uniquely determined. In the first case each of the right-up diagonals will contain the same number with each of the number repeating on every third diagonal. In the second case each of the right-down diagonals will contain the same number with each number repeating on every third diagonal. In both cases the array will be filled correctly since it will not be possible for the tile to cover the same number twice.
We conclude that there are two ways to fill the array in this way. Allowing for permutations, there are 26=122 \cdot 6 = 12 solutions.

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.