Maths Olympiad Prep

Library / /17 of 19

Combinatorics Difficulty 6.9 National olympiad Prove it North Macedonia

A 5×55 \times 5 board, consisting of 25 unit squares, a positive integer k25k \le 25 and an unlimited supply of LL-shapes are given. Two players, AA and BB, play the following game: starting with AA they alternatively mark a previously unmarked unit square until they mark a total of kk unit squares.

We say that a placement of LL-shapes on unmarked unit squares is called good if the LL-shapes do not overlap and each of them covers exactly three unmarked unit squares of the board. BB wins if every good placement of LL-shapes leaves uncovered at least three unmarked unit squares. Determine the minimum value of kk for which BB has a winning strategy.

Solution

If k=1k=1, player AA marks the upper left corner of the square and then fills it as follows.

If k=2k=2, player AA marks the upper left corner of the square. Whatever square player BB marks, then player AA can fill in the square in exactly the same pattern as above except that he doesn't put the trimino which covers the marked square of BB. Player AA wins because he has left only two unmarked squares uncovered.

For k=3k=3, player AA wins by following the same strategy. When he has to mark a square for the second time, he marks any yet unmarked square of the triomino that covers the marked square of BB.

Let us now show that for k=4k=4 player BB winning strategy. Since there will be 21 unmarked squares, player AA will need to cover all of them with seven LL-shaped triominoes. We can assume that in his first move, player AA does not mark any square in the bottom two rows of the chessboard (otherwise just rotate the chessboard). In his first move player BB marks the square labeled 1 in the following figure.

If player AA in his next move marks the squares 2 then player BB marks the square labeled 5. Player BB wins as the square labeled 3 is left unmarked but cannot be covered with an LL-shaped triomino.

Finally, if player AA in his next move marks one of the squares labeled 3 or 4, player BB marks the other of these two squares. Player BB wins as the square labeled 2 is left unmarked but cannot be covered with an LL-shaped triomino.

Since we have covered all possible cases, player BB wins when k=4k=4.

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.