FreeBrainteaserMedium

Moving The Piece I

Asked atCitadelOptiver

A piece starts on the top-left square of a grid with $183$ rows and $181$ columns. Alice and Bob take turns moving it to a neighbouring square; diagonal neighbours count. The piece may never move onto a square it has already visited, including the starting square. The player who cannot move loses. Alice moves first. Who has a winning strategy?

Solution

Try it yourself first. Open a hint if you get stuck.

Hint 1

Try to split every square except the start into pairs of neighbouring squares.

Hint 2

If such a pairing exists, how can Bob answer each of Alice's moves?

Show solution

Bob wins by pairing squares.

Step 1: Pair up every square except the start. The grid has $183 \times 181$ squares, an odd number, so leaving out the starting corner leaves an even number. Pair them like this:

Top row: the start is column $1$ . Pair columns $2$ – $3$ , $4$ – $5$ , $\dots$ , $180$ – $181$ side by side ( $90$ pairs).
Every other row: rows $2$ to $183$ are $182$ rows, an even number. Pair rows $2$ – $3$ , $4$ – $5$ , $\dots$ , $182$ – $183$ , each square with the one directly below it.

Every square except the start is now in exactly one pair, and the two squares of each pair are neighbours.

Step 2: Bob's strategy. Whenever Alice moves onto a square, Bob moves onto that square's partner.

Why this always works. After each of Bob's moves, the visited squares are the start plus some complete pairs. So when Alice moves to an unvisited square, its partner is unvisited too, and it is a neighbour of where the piece now stands. Bob always has a legal move.

The game must end, because squares run out. Since Bob can always answer Alice, Alice is the one who gets stuck.

Answer: Bob wins.

Note: the diagonal moves don't matter here. Bob only ever uses straight moves, and Alice's extra options can't break the pairing.

Question

Solution