Maths Olympiad Prep

Library / /346 of 520

Combinatorics Difficulty 5.5 AIME, harder Find the answer

6. On a 200×200200 \times 200 chessboard, some cells contain a red or blue piece, while others are empty. If two pieces are in the same row or column, we say one piece can "see" the other. Assume each piece can see exactly five pieces of the opposite color (it may also see some pieces of the same color). Find the maximum number of pieces on the chessboard.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

6. First, give an example with 3800 pieces.

The intersections of rows 1 to 5 and columns 11 to 200, as well as the intersections of columns 1 to 5 and rows 11 to 200, are all placed with red pieces; the intersections of rows 6 to 10 and columns 11 to 200, as well as the intersections of columns 6 to 10 and rows 11 to 200, are all placed with blue pieces. It is easy to verify that each piece can see exactly five pieces of the opposite color. At this point, the total number of pieces is
5×190×4=3800. 5 \times 190 \times 4 = 3800 \text{.}

Now assume there is a valid placement of pieces such that the total number of pieces on the board exceeds 3800. In this case, connect each piece to the pieces it can see with edges, so that the number of edges connected to each piece is exactly 5. Thus, the total number of edges exceeds
12×5×3800=9500. \frac{1}{2} \times 5 \times 3800 = 9500.

Consider any row: if there are no pieces of the opposite color in that row, then the number of pieces in that row does not exceed 200, and the number of edges is 0; if there are pieces of the opposite color in that row, suppose there is a red piece R R and a blue piece B B . Since the red piece R R can see exactly five pieces of the opposite color, there can be at most five blue pieces in that row. Similarly, there can be at most five red pieces in that row. Therefore, the number of pieces in that row does not exceed 10, and the number of edges does not exceed 25.

If there are 191 rows containing pieces of the opposite color, then the total number of pieces on the board does not exceed
191×10+9×200<3800, 191 \times 10 + 9 \times 200 < 3800,
which contradicts the assumption. This indicates that there are at most 190 rows containing pieces of the opposite color. Thus, the number of edges connecting pieces of the opposite color in the same row does not exceed 190×25=4750 190 \times 25 = 4750 .
Similarly, the number of edges connecting pieces of the opposite color in the same column does not exceed 4750.
Therefore, the total number of edges does not exceed
2×4750=9500, 2 \times 4750 = 9500 \text{,}
which also leads to a contradiction.
This shows that the total number of pieces on the board must not exceed 3800. In summary, the maximum value sought is 3800.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.