Find all positive integers (Solution problem 4 about combinatoric in Shortlist problem in IMO 2016 )
Problem Combinatoric 4 :
Find all positive integers n for which we can fill in the entries of an n x n table with the following properties:
- each entry can be one of I, M and O;
- in each row and each column, the letters I, M and O occur the same number of times; and
- in any diagonal whose number of entries is a multiple of three, the letters I, M and O occur the same number of times.
Answer : n can be any multiple of 9.
We first show that such a table exists when n is a multiple of 9. Consider the following 9 x 9 table.
It is a direct checking that the table (1) satisfies the requirements. For n = 9k where k is a positive integer, we form an n x n table using k x k copies of (1). For each row and each column of the table of size n, since there are three I’s, three M’s and three O’s for any nine consecutive entries, the numbers of I, M and O are equal. In addition, every diagonal of the large table whose number of entries is divisible by 3 intersects each copy of (1) at a diagonal with number of entries divisible by 3 (possibly zero). Therefore, every such diagonal also contains the same number of I, M and O.
Next, consider any n x n table for which the requirements can be met. As the number of entries of each row should be a multiple of 3, we let n = 3k where k is a positive integer. We divide the whole table into k x k copies of 3 x 3 blocks. We call the entry at the centre of such a 3 x 3 square a vital entry. We also call any row, column or diagonal that contains at least one vital entry a vital line. We compute the number of pairs (l; c) where l is a vital line and c is an entry belonging to l that contains the letter M. We let this number be N. On the one hand, since each vital line contains the same number of I, M and O, it is obvious that each vital row and each vital column contain k occurrences of M. For vital diagonals in either direction, we count there are exactly
occurrences of M. Therefore, we have .
On the other hand, there are occurrences of M in the whole table. Note that each entry belongs to exactly 1 or 4 vital lines. Therefore, N must be congruent to mod 3.
From the double counting, we get (mod 3), which forces k to be a multiple of 3. Therefore, n has to be a multiple of 9 and the proof is complete.