Maths Olympiad Prep

Library / /25 of 46

Combinatorics Difficulty 6.2 National olympiad Prove it Russia

In several cells of a 10×1010 \times 10 grid either a cross or a nought is placed. It appeared that there is no column or row occupied with 1010 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 AA 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 AA 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.

Figure 1

Fig. 11

Figure 2

Fig. 12

Suppose there are more than two empty cells. Then for two of them (say, AA and BB), 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 AA and the column containing BB, 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 9898.

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.