Maths Olympiad Prep

Library / /4 of 4

Combinatorics Difficulty 9.0 IMO level Prove it Estonia

Let nn be a positive integer. In how many ways can an n×nn \times n table be filled with integers from 00 to 55 such that

a) the sum of each row is divisible by 22 and the sum of each column is divisible by 33;

b) the sum of each row is divisible by 22, the sum of each column is divisible by 33 and the sum of each of the two diagonals is divisible by 66?

Solution

a) Let's fill the top left (n1)×(n1)(n-1) \times (n-1) subtable arbitrarily; this can be done in 6(n1)26^{(n-1)^2} ways. Now there are 33 ways to fill each of the top n1n-1 cells of the rightmost column and 22 ways to fill each of the left n1n-1 cells of the bottom row to satisfy the requirements. The value for the last empty cell in the bottom right is then uniquely determined (mod 22 by the bottom row, and mod 33 by the rightmost column). In conclusion, there are 6(n1)23n12n1=6n2n6^{(n-1)^2} \cdot 3^{n-1} \cdot 2^{n-1} = 6^{n^2-n} ways to fill the table.

b) For n=1n=1, the only solution is writing 00 into the single cell. For n=2n=2, let aa be the top left number. The bottom right must then be (6a)(6-a) mod 66. Using the conditions for rows and columns, for the top right number xx we get the equations xa(mod2)x \equiv -a \pmod{2} and xa(mod3)x \equiv a \pmod{3}, and for the bottom left number yy, ya(mod2)y \equiv a \pmod{2} and ya(mod3)y \equiv -a \pmod{3}. The Chinese remainder theorem determines xx and yy uniquely, and we see from the equations that their sum is also divisible by 66. Thus there are 66 ways to fill the table in this case, one for each value of aa.

Consider now n3n \ge 3. Fill the top left (n1)×(n1)(n-1) \times (n-1) subtable arbitrarily; this can be done in 6(n1)26^{(n-1)^2} ways. The bottom right cell's value is uniquely determined by other values on the falling diagonal. Denote the value in the top left cell by aa, the sum of the 22nd to (n1)(n-1)-st cells (inclusive) in the top row by bb, the sum of the 22nd to (n1)(n-1)-st cells in the leftmost column by cc, and the sum of 22nd to (n1)(n-1)-st cells on the rising diagonal by dd.

Using the Chinese remainder theorem, fill the top right cell with the unique value xx such that xab(mod2)x \equiv -a-b \pmod 2 and xa+cd(mod3)x \equiv a+c-d \pmod 3, and the bottom left cell with the unique value yy such that ya+bd(mod2)y \equiv a+b-d \pmod 2 and yac(mod3)y \equiv -a-c \pmod 3. The divisibility conditions are now fulfilled for the top row, the leftmost column and both diagonals (the rising diagonal is verified by summing mod 22 and mod 33 separately).

Now, we leave one cell both in the rightmost column and in the bottom row empty for the time being. For the other n3n-3 empty cells in the rightmost column, there are 33 possible values for each, and for the other n3n-3 empty cells in the bottom row, 22 values for each. Having made all those choices (which can be done in 3n32n33^{n-3} \cdot 2^{n-3} ways), the values for the two remaining cells are now uniquely determined (mod 22 by the values in the respective row, and mod 33 by the column). The total number of ways to fill the table is 6(n1)23n32n3=6n2n26^{(n-1)^2} \cdot 3^{n-3} \cdot 2^{n-3} = 6^{n^2-n-2}.

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 and solution reproduced as published; topic and difficulty added by this site.