Maths Olympiad Prep

Library / /19 of 22

Combinatorics Difficulty 8.9 Shortlist Prove it Germany

Problem:

The 16 squares of a 4×44 \times 4 chessboard can be arranged into 18 lines as follows: the four rows, the four columns, five diagonals from northwest to southeast, and five diagonals from northeast to southwest. Here these diagonals consist of 2, 3, or 4 squares of the same color that are corner-adjacent to one another; thus the corner squares of the chessboard alone do not form a diagonal.

Now a game piece is placed on each of 10 of the 16 squares. Each of the 18 lines that then contains an even number of pieces scores one

Figure 1

point.

What is the largest score achievable by placing the 10 game pieces? Justify your answer.

Solution

Solution:

The largest achievable score is 17, as shown by the example pictured. It remains to show that the maximum score of 18 cannot be achieved. To this end, we assume the existence of a placement achieving 18 points and first consider the rows and columns. Neither in a row nor in a column can there then lie an odd number of pieces, so that, because of the sum 10, only (up to permutations) the possibilities (4;2;2;2)(4; 2; 2; 2) or (4;4;2;0)(4; 4; 2; 0) can occur. However, if there is a row (column) with 0 pieces, then all columns (rows) can contain at most 2 pieces because of the required evenness, so that the sum 10 is not reached. Therefore there is exactly one row and one column with 4 pieces. The intersection point of these

Figure 2

17 points

Figure 3
Case a)
Figure 4
Case b)
Figure 5
Case c)

two lines can now lie a) in a corner, b) on the edge, but not in a corner, c) in the interior of the square. Because of symmetry, it suffices to consider one example each.

Case a): Here the five NW-SE lines each contain, at this point, only one piece. But since only three more pieces are to be placed, the score of 18 can no longer be achieved.

Case b): Here four of the NW-SE lines each contain, at this point, only one piece. But since only three more pieces are to be placed, the score of 18 can no longer be achieved.

Case c): The two NW-SE lines with exactly 2 squares each contain, at this point, only one piece. If a second piece is placed on them, then the upper SW-NE line with 3 pieces scores no point. Here too the score of 18 is not achieved.

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 translated into English from de; metadata (topic, difficulty) added by this project.