4
$\begingroup$

Alice and Bob are playing the neighbouring game

which is originally single game to get the highest point at the end.

You start with an empty 4x4 grid. At each turn you can choose an empty cell and place a value in it. The placed value is given by the following rules:

  • If the chosen cell has no neighboring (horizontal or vertical) values then the placed value is 1.
  • Otherwise the placed value is the sum of all neighboring (horizontal or vertical) values.

But this time, Alice and Bob are trying to get the highest total point by summing the values they put on the board with the rules by the Neighbouring Game. Alice puts a value on the board then next turn Bob puts and the game goes on. Alice starts the game with putting 1 somewhere on this 4x4 grid table, then Bob continues.

Who is likely to win the game at the end?

$\endgroup$
11
$\begingroup$

The answer is

Bob always wins.

How?

Divide the grid into 8 dominoes:

AABB
CCDD
EEFF
GGHH

Then, whenever Alice picks a cell, Bob plays the neighboring cell that is part of the same domino. Bob's number is always Alice's number plus whatever extra surrounding numbers the cell has, and at the last turn there will always be some surrounding numbers. Therefore, Bob's total is always higher than Alice's.

Generalization:

For a rectangular board of any size, Alice wins if the board contains odd number of cells (width and height are both odd) and Bob wins otherwise.

Because:

The domino covering argument applies to even×even or even×odd boards, so Bob wins. For an odd×odd board, Alice takes the top left corner cell in her first turn. Then the rest of the board is known to have a domino tiling, so Alice wins.

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