Browse · MathNet
PrintChina Girls' Mathematical Olympiad
China counting and probability
Problem
For a chessboard of the size , in each case (they all have different colors) write one of the letters . If every square contains all these four letters, we call it a "harmonic chessboard." How many different harmonic chessboard are there? (Posed by Zuming Feng)
Solution
There are harmonic chessboards. We first prove the following claim:
In every harmonic chessboard, at least one of the following two situations occurs: (1) each line is composed of just two letters, in an alternative way; (2) each column is composed of just two letters, in an alternative way.
In fact, suppose that one line is not composed of two letters; then there must be three consecutive squares containing different letters. Without loss of generality, we may assume these three letters to be , as shown in Fig. 1. We then get easily , and , as shown in Fig. 2.
Fig. 1 Fig. 2
The same argument shows that each of these three columns is composed of two letters in an alternative way, and a fortiori so is every column.
Now we calculate the total number of different harmonic chessboards. If the leftmost column is composed of two letters (eg. and ), we see immediately that all the odd-numbered columns are composed of these two letters, while the even-numbered columns are composed of the other two letters. The letter in the top square of each column can be either of the two letters that compose this column; we check easily that it is a harmonic chessboard. Therefore, we have different ways to choose the two letters of the first column, and ways to determine the letter in the top square of each column. Hence, we get configurations to make each column composed of two letters in an alternative way. We have also configurations to make each line composed of two letters in an alternative way.
Then we need to subtract from the sum the configurations that are counted twice, i.e. the configurations that are alternative on each line and each column. Obviously, any such configuration is in one-to-one correspondence to the square at the upper-left corner, which gives different ways. Hence, we get the above result.
In every harmonic chessboard, at least one of the following two situations occurs: (1) each line is composed of just two letters, in an alternative way; (2) each column is composed of just two letters, in an alternative way.
In fact, suppose that one line is not composed of two letters; then there must be three consecutive squares containing different letters. Without loss of generality, we may assume these three letters to be , as shown in Fig. 1. We then get easily , and , as shown in Fig. 2.
Fig. 1 Fig. 2
The same argument shows that each of these three columns is composed of two letters in an alternative way, and a fortiori so is every column.
Now we calculate the total number of different harmonic chessboards. If the leftmost column is composed of two letters (eg. and ), we see immediately that all the odd-numbered columns are composed of these two letters, while the even-numbered columns are composed of the other two letters. The letter in the top square of each column can be either of the two letters that compose this column; we check easily that it is a harmonic chessboard. Therefore, we have different ways to choose the two letters of the first column, and ways to determine the letter in the top square of each column. Hence, we get configurations to make each column composed of two letters in an alternative way. We have also configurations to make each line composed of two letters in an alternative way.
Then we need to subtract from the sum the configurations that are counted twice, i.e. the configurations that are alternative on each line and each column. Obviously, any such configuration is in one-to-one correspondence to the square at the upper-left corner, which gives different ways. Hence, we get the above result.
Final answer
12 * 2^2008 - 24
Techniques
Inclusion-exclusionColoring schemes, extremal arguments