Moe and Joe are playing following game on a $100 \times 100$ squared board. Moe and Joe each take turns placing out their gamepiece. Moe's piece is a $2 \times 2$ Square, and Joe's piece is an "L" made up of small squares ($2 \times 2$ square, without a top-right corner). The person who can not longer place their piece on the $100 \times 100$ game board loses.
(a) Does either Moe or Joe have a winning strategy, if Moe places the first piece (i.e a $2 \times 2$ square)?
(b) Does either Moe or Joe have a winning strategy, if Joe places the first piece (the "L" piece)?
I have stared at this question a long time, and I do not really know how I should attack this problem. I would really appreciate some help.
For the notation I will assume that the board has coordinates $(x,y)$ with $1\leq x\leq 100$ and $1\leq y \leq 100$. I will refer to a piece as a set of coordinates.
If Joe places the first piece, he has a winning strategy as follows:
In the first turn he places his piece offset at the bottom left corner at $\{(2,2),(2,3),(3,2)\}$. Then he proceeds to play as follows:
This is winning. First, it is easy to see that the move in the second case is always available, since Moe cannot block any of the squares in $\{(1,1),(2,1),(1,2)\}$ as $(2,2)$ is occupied by Joe's first move but would necessarily be covered by Moe's piece. Then, once the second case is entered, Moe has no available move left because we only enter the second case if we cannot place an L-piece anywhere else. Since the square tile is strictly larger, this means Moe cannot put a square piece anywhere either. Formally, we can say that each L-piece is a subset of a square piece, i.e., $\{(n,m),(n+1,m),(n,m+1)\}\subset \{(n,m),(n+1,m),(n,m+1),(n+1,m+1)\}$
If Moe places the first piece we can adapt the strategy.
If we are allowed to turn the L-piece, this is straight forward. Just do the same strategy in another corner, i.e., replace $1, 2, 3$ by $100, 99, 98$, respectively.
If we are not allowed to turn the L-piece, we have to do a little more work.
Case 1: Moe does not occupy any square in $\{(2,2),(2,3),(3,2),(1,1),(2,1),(1,2)\}$. Then Joe can employ the same strategy as in the case where Joe starts.
Case 2: Moe starts by placing a square on $\{ (1,1),(1,2),(2,1),(2,2) \}$. Then Joe can employ a similar strategy, starting with an L-piece at $\{(2,3),(2,4),(3,3)\}$. This leaves a gap at $\{(1,3),(1,4),(2,3)\}$ where Joe can place an L-piece, but Moe cannot place a square piece oppupying either of those 3 squares. So again Joe avoids placing a piece there as long as possible, and as soon as no other move is available, places his piece at $\{(1,3),(1,4),(2,3)\}$, guaranteeing that Moe does not have another move.
There are seven more cases now, depending on which square Moe starts on. They are more or less the same as case 2. One slightly different case is when Moe starts on $\{(2,2),(2,3),(3,2),(3,3)\}$. Then this already creates the L-shaped gap at $\{ (1,1),(1,2),(2,1) \}$ for Joe, so he can continue the game as if he started.