6
$\begingroup$

On a $9\times10$ checkerboard with $90$ squares, a game proceeds as follows:

  • First, you place $x$ rocks on the board. Each rock occupies a single square. No rock may touch the edge of the checkerboard. No rock may be positioned diagonally adjacent to another rock (while positioning them vertically or horizontally adjacent is allowed).

  • The snake chooses an empty square on the board as its starting point. It moves around by always moving to a (horizontally or vertically, but not diagonally) adjacent square. It must not visit any square twice, and it can not visit any square that is occupied by a rock.

The snake wins the game, if it manages to visit every empty square on the board exactly once. Assume that the snake is a perfect player.

Questions:

  1. What is the minimum number of rocks required to prevent the snake from winning, and how will you place them?

  2. A harder question: What if the aim of the snake is to visit every empty square exactly twice?

$\endgroup$
18
$\begingroup$

The answer to the first question is:

Two rocks are sufficient to prevent the snake from winning.

Proof: Use the standard black-and-white checkerboard coloring, and put the rocks on two white squares (while obeying the rules on placing the rocks). Then there are 43 empty white squares and 45 empty black squares. Since the snake alternately moves between black and white squares, in its altogether 88 moves it must visit 44 white and 44 black squares. Impossible.

A single rock is not sufficient to prevent the snake from winning.

On the totally empty checkerboard, there exists a closed tour that visits every square exactly once and that ends again at the starting point. Putting a single rock onto the board would cut the closed tour at one point; the snake could use the remaining piece of the tour to visit every square exactly once.


For the second (harder) question the answer is:

A single rock is sufficient to prevent the snake from winning.

Use the same argument as above: a single rock placed on an arbitrary white square would force the snake to visit $2\cdot44$ empty white squares and $2\cdot45$ empty black squares. Impossible.

$\endgroup$
5
$\begingroup$

For the first part, 4 rocks should be sufficient: the rocks are in a line, 1 space between each, and all are 1 space from the edge. Effectively, this creates a graph with 3 nodes with 3 entry points, which can't be properly traversed.

I'll think about the second question...

$\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.