Browse · MathNet
PrintFinal Round of National Olympiad
Estonia counting and probability
Problem
Define magic square as a table where each cell contains one number from to so that all these numbers are used and all row sums and column sums are equal. Prove that any two magic squares can be obtained from each other via the following transformations: interchanging two rows, interchanging two columns, rotating the square, reflecting the square w.r.t. its diagonal.
Solution
As all the transformations are invertible, it suffices to show that every magic square can be turned to one particular magic square by these transformations.
Figure 29
Figure 30
The sum of all numbers in a magic square is , whence the numbers in each row and each column must sum up to . As this is odd, exactly or of the three summands must be even. There are even numbers in use, hence even numbers must be in some two rows and even number in the remaining one. The same holds for columns. Hence the even numbers , , , occur in the corners of some rectangle with sides parallel to the edges of the table. By interchanging rows or columns one can move the even numbers to the corners of the whole table. There are possibilities to locate these four numbers into the corners, that can not be obtained from each other by rotations and reflections of the table (Fig. 29). The last two of them cannot occur in the magic square because the missing numbers in the first and third column would coincide. Hence only the first possibility remains. Its completion to a magic square is unique (Fig. 30).
| 2 | 4 | |
| 6 | 8 |
| 2 | 4 | |
| 8 | 6 |
| 2 | 6 | |
| 8 | 4 |
| 2 | 9 | 4 |
| 7 | 5 | 3 |
| 6 | 1 | 8 |
The sum of all numbers in a magic square is , whence the numbers in each row and each column must sum up to . As this is odd, exactly or of the three summands must be even. There are even numbers in use, hence even numbers must be in some two rows and even number in the remaining one. The same holds for columns. Hence the even numbers , , , occur in the corners of some rectangle with sides parallel to the edges of the table. By interchanging rows or columns one can move the even numbers to the corners of the whole table. There are possibilities to locate these four numbers into the corners, that can not be obtained from each other by rotations and reflections of the table (Fig. 29). The last two of them cannot occur in the magic square because the missing numbers in the first and third column would coincide. Hence only the first possibility remains. Its completion to a magic square is unique (Fig. 30).
Techniques
Enumeration with symmetryInvariants / monovariantsColoring schemes, extremal arguments