Maths Olympiad Prep

Library / /45 of 45

, 2008

Combinatorics Difficulty 7.3 National olympiad, round 2 Prove it Slovenia

Two players share a pile of coins, alternating in taking one coin off the pile and placing it on any empty square of a 2008×20082008 \times 2008 chessboard. The player who puts the coin onto the board in such a way that together with three other coins already on the board it forms a non-rectangular isosceles trapezoid with bases parallel to two of the edges of the board, wins. Which of the players has the winning strategy – the first or the second?

Solution

Let us call a non-rectangular isosceles trapezoid with the bases parallel to two of the edges of the board regular. We show that the second player can always win. After the first player's every move the second player should check to see if they can form a regular trapezoid by the placing of a single coin. If not, the second player should put the coin onto the board in such a way, that after their move the arrangement of the coins will have the vertical line across the middle of the board as its axis of symmetry (i.e. the second player's move mirrors the first player's move with regard to this line).

Assume that the first player wins by placing a coin onto the square which we denote by a0a_0. Let a1,a2a_1, a_2 and a3a_3 denote the other three squares that together with a0a_0 form a regular trapezoid (i.e. all four are different and each contains a coin). Let b0,b1,b2b_0, b_1, b_2 and b3b_3 be the corresponding mirror images. Squares b1,b2b_1, b_2 and b3b_3 contain coins and b0b_0 is empty. First, we show that none of the squares a0,a1,a2,a3,b0,b1,b2a_0, a_1, a_2, a_3, b_0, b_1, b_2 and b3b_3 coincide.

Since the length of the board is even, we have aibia_i \neq b_i for all i=0,1,2,3i = 0, 1, 2, 3. If ai=bja_i = b_j for some iji \neq j, then bi=ajb_i = a_j, so the side aiaja_i a_j of the trapezoid a0a1a2a3a_0 a_1 a_2 a_3 is horizontal. If this is the case, the side akala_k a_l for {k,l}={0,1,2,3}{i,j}\{k,l\} = \{0,1,2,3\} \setminus \{i,j\} is also horizontal, because a regular trapezoid has no right angles. Since this trapezoid is isosceles, we get bk=alb_k = a_l and al=bka_l = b_k for lkl \neq k. This implies b0=amb_0 = a_m for some m0m \neq 0. A contradiction, the square b0b_0 is empty and squares a1,a2,a3a_1, a_2, a_3 contain coins.

Hence, all those squares are necessarily different and before the first player made his or her last move the triples a1,a2,a3a_1, a_2, a_3 and b1,b2,b3b_1, b_2, b_3 were covered with coins. This implies that at least one of the triples was covered with coins before the second player made his or her last move, so following the strategy the second player should already have won.

Figure 1

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.