Let be a positive integer. We wish to inscribe into each square of the array one of the numbers , or , 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?
, 2016
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 , and will also give us a correct solution. We can put the numbers , and in different orders, namely , , , , and .
So, we have to count the arrays which contain , , , in this order, in the first three squares of the first row, and multiply the result by .
Placing , and in the first three squares of the first row gives us two possibilities for the first square of the second row, or . In both cases the remainder of the upper left square is then uniquely determined and is
| 1 | 2 | 3 |
|---|---|---|
| 2 | 3 | 1 |
| 3 | 1 | 2 |
| 1 | 2 | 3 |
|---|---|---|
| 3 | 1 | 2 |
| 2 | 3 | 1 |
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 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.