6
$\begingroup$

Alice and Bob play a game by alternately placing dominoes on a $3\times100$ checkerboard (3 rows, 100 columns). Alice has the first move.

  • A move of Alice consists in placing a $1\times2$ (horizontal) white dominoe.
  • A move of Bob consists in placing two $2\times1$ (vertical) black dominoes.

The dominoes must be placed without overlaps, and they must always cover exactly two cells of the checkerboard. The loser is the player who cannot make a complete move.

Determine the winner of the game. (As usual, we assume that Alice and Bob use optimal strategies.)

$\endgroup$
  • $\begingroup$ Are the rules of standard dominoes in play as well? $\endgroup$ – Kevin - Reinstate Monica Feb 8 '15 at 9:10
3
$\begingroup$

Alice can win using the following strategy: if possible, place a domino in the leftmost available place in the middle row. If it is not possible to play in the middle row, place a domino directly above or below one previously placed in the middle row.

First, I claim that Alice will be able to play at lease 17 dominos in the middle row. To see why, note that there are initially 99 places a domino can go in the middle row. Call such a place blocked if one or both of its squares is occupied by another domino. Each domino Alice or Bob places blocks at most 2 previously unblocked places (so that Bob can block at most 4 places on each of his turns). 16 turns by Alice and 16 turns by Bob lead to at most $16\cdot 2+16\cdot 4 =96$ of the 99 places being blocked, so Alice can still find a place to play in the middle row on her 17th turn.

Each domino placed in the middle row makes space for two more dominos, one above it and one below it, and Bob cannot interfere with these spaces. So after playing 17 dominos in the middle row, Alice is guaranteed to be able to find a play for the next 34 turns. This gives Alice a total of at least 51 plays.

Finally, Bob will not be able to play 51 times. In 51 turns, Bob would need to place 102 dominos. Each domino Bob places must be in a different column, and there are only 100 columns on the board.

In fact, Bob cannot play in any of the (at least) 34 columns containing one of Alice's middle row dominos, so Bob will actually be able to take a total of at most 33 turns.

$\endgroup$
4
$\begingroup$

Alice wins.
Starting out Alice has 150 possible locations to place, and Bob has 100. If Alice places 1 domino along the middle row she will eliminate two possible locations for Bob. If Bob places 2 dominoes spaced one from eachother and one from Alice's piece, he will eliminate 4 spots for alice. Repeated over the board this strategy will for the first 96 columns remove 32 spots from Bob, and 64 from Alice, the final 4 columns removes 2 from Bob and 2 from Alice leaving Bob with 1 piece left in his move. Now there are 84 locations left for Alice of which 34 are untouchable for Bob. Bob has 68 locations of which 16 are untouchable. Since Bob has 1 domino left of his turn, and Bob will use 2 locations for every Alice's one (2*34=68), Alice will win even if she doesn't place in any of Bob's remaining spots, which she of course will.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.