In several cells of a grid either a cross or a nought is placed. It appeared that there is no column or row occupied with signs of the same type, but if one places any sign into any empty cell, this condition would fail. Find the least possible number of cells occupied with signs.
Solution
Let us fill the table according to the condition, and let cell be empty. Since placing any sign in it would create a row or column filled with identical signs, there must exist a line (row or column) containing in which all other cells are filled with crosses, and the same is true for noughts (these lines must, of course, be a row and a column). In particular, all empty cells are in different rows and columns.

Fig. 11

Fig. 12
Suppose there are more than two empty cells. Then for two of them (say, and ), the direction of the line of crosses coincides (that is, either for both the crosses are in their rows, or for both in their columns) (see Fig. 11). Suppose the crosses are in their columns, and the noughts are in their rows; then at the intersection of the row containing and the column containing , there must be both a cross and a nought (since this intersection is not empty); contradiction. Therefore, there are at most two empty cells. An example with two empty cells is shown in Fig. 12 (any signs can be placed instead of the asterisks).
Thus, the least possible number of cells occupied with signs is .