11. Mike and Harry play a game on an $8 \times 8$ board. For some positive integer $k$, Mike chooses $k$ squares and writes an $M$ in each of them. Harry then chooses $k+1$ squares and writes an $H$ in each of them. After Harry is done, Mike wins if there is a sequence of letters forming " $H M M$ " or "MMH," when read either horizontally or vertically, and Harry wins otherwise. Determine the smallest value of $k$ for which Mike has a winning strategy.
Answer: 16
Suppose Mike writes $k M$ 's. Let $a$ be the number of squares which, if Harry writes an $H$ in, will yield either $H M M$ or $M M H$ horizontally, and let $b$ be the number of squares which, if Harry writes an $H$ in, will yield either $H M M$ or $M M H$ vertically. We will show that $a \leq k$ and $b \leq k$. Then, it will follow that there are at most $a+b \leq 2 k$ squares which Harry cannot write an $H$ in. There will be at least $64-k-2 k=64-3 k$ squares which Harry can write in. If $64-3 k \geq k+1$, or $k \leq 15$, then Harry wins.
We will show that $a \leq k$ (that $b \leq k$ will follow by symmetry). Suppose there are $a_{i} M$ 's in row $i$. In each group of 2 or more consective $M$ 's, Harry cannot write $H$ to the left or right of that group, giving at most 2 forbidden squares. Hence $a_{i}$ is at most the number of $M$ 's in row $i$. Summing over the rows gives the desired result.
Mike can win by writing $16 \mathrm{M}$ 's according to the following diagram: