Alex and Katy play a game on an $8 \times 8$ square grid made of 64 unit cells. They take it in turns to play, with Alex going first. On Alex's turn, he writes 'A' in an empty cell. On Katy's turn, she writes ' $\mathrm{K}$ ' in two empty cells that share an edge. The game ends when one player cannot move. Katy's score is the number of Ks on the grid at the end of the game. What is the highest score Katy can be sure to get if she plays well, no matter what Alex does?
SolUTION
Katy's maximum score is 32 .
She can achieve this by dividing the board into $2 \times 1$ rectangles at the start of the game. On each of her turns she can place two Ks into an empty one of these rectangles. On Alex's turns he can reduce the number of empty $2 \times 1$ rectangles by at most 1 . This means each player will have at least sixteen turns, giving Katy a final score of at least 32 .

Alex can prevent Katy from scoring more than 32 as follows. He colours the board in the standard chessboard pattern and then promises to only ever place As on cells that are (say) black. This means that Alex and Katy each cover exactly one black cell each turn, so they can take at most 16 turns each, giving Katy a maximum possible score of 32 .

REMARK
The delicate thing in questions of this type is to ensure that the strategies described for each player do not depend on the other playing following a particular 'sensible' strategy.

REMARK
There are other ways to describe good strategies for Katy. She might, for example, divide the board into sixteen $2 \times 2$ squares and whenever Alex places a first A in such a square, use her next move to place two Ks in that square.