Consider two friends, Alice and Bob, playing a game on a $1000 \times 1000$ board. Alice's game piece consists of a $2 \times 2$ square while Bob has to content himself with $3$ squares put together in L-form. They can emplace, turn by turn, their game pieces wherever they prefer on the board and whenever one can't emplace his/her game piece on the board, he/she has lost the game.

Is there any winning strategy for Alice or Bob?

I can't make any conclusions about this teaser. I had one idea which aimed to color the board in a $1000 \times 1000$ checkered pattern. So, color the board in a dark and light checkered pattern. We then notice that Alice always, i.e., in every move, covers two black and two white squares, while Bob covers two of one color and only one of the other. So Bob can decide to only cover two dark squares and one light square. Then the dark squares will be cancelled out more quickly, which should favor Bob.

However, I really can not convince myself about this strategy. Is it possibly so, that I'm on the right track?

Another idea would be to notice that Bob could make such moves that he blocks Alice to place her game piece at some squares at the first or last row/column.

If we, for instance, numerate every square $s=(r, c)=(\textrm{row, column})$, then Bob could emplace his game piece at $(3,1), (3,2), (2, 2)$ and block Alice to emplace her game piece at $(1, 1) , (1, 2), (2, 1)$. But Bob would always be able to emplace his game piece at these squares.

What do you think? Who has a winning strategy? Maybe a combinatorial argument could solve the question?


1 Answer 1


Bob can win using the strategy you hint at. After Alice makes the first move, he will be able to move in at least three corners as you describe in the next to last paragraph. He should move in one on his first move. After that he refuses to play in that corner until he has no other choice. Anywhere Alice can move, Bob can move too. If he comes to a point he has no other choice besides the corner, Alice will not be able to move and he wins. He might win without using the corner as well.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .