# Optimal moves for maximizing perimeter? [closed]

Herman and Alex play a game on a $$5 \times 5$$ board. On his turn, a player can claim any open square as his territory. Once all the squares are claimed, the winner is the player whose territory has the longer border. Herman goes first. If both play their best, who will win, or will the game end in a draw?

Any help would be appreciated.

Source: Washington's Monthly Math Hour, 2014 ## closed as off-topic by user21820, Cesareo, Alex Provost, Saad, Xander HendersonMar 23 at 14:41

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – user21820, Cesareo, Alex Provost, Saad, Xander Henderson
If this question can be reworded to fit the rules in the help center, please edit the question.

• How is the length of the border computed? If the players choose their squares like a $5\times5$ checkerboard, what is the length of the two borders? – saulspatz Mar 10 at 23:43
• Possible hint. What if they play on a $3 \times 3$ board, H takes the central square and then plays A's move rotated through half a circle? – Ethan Bolker Mar 10 at 23:44
• @EthanBolker I wonder. If A plays orthogonally adjacent to the center, and H follows suit, the border of A's area is $4$ and that of B's area is $6.$ Then A plays opposite his first square, H follows suit, and they are tied at $8$ all. Now the board is completely symmetric, so it ends in a draw. (Assuming I understand how to calculate the length of the border, at least.) – saulspatz Mar 10 at 23:53
• @saulspatz H plays first at center, A plays orthogonal to the center. Then H plays opposite A, so A can't play there next. It's hard for me to see how H's extra center square plus the symmetry can be a loss for H.(It's confusing to me that H is what I would call B, and that H goes first. Standard conventions would be better.) – Ethan Bolker Mar 11 at 0:12
• @EthanBolker Yes, I shouldn't have said A plays opposite at his second move, just that he again plays orthogonally adjacent to the center. It seems to me that this leads to a draw. I didn't mean H would lose, just that there might be some other strategy that would give him a win. I agree with you about the names. – saulspatz Mar 11 at 1:34

## 1 Answer

I will call the players $$A$$ and $$B$$.

The game is made trivial by the following observation. Let $$s_A$$ and $$s_B$$ be the final scores of the two players. Let $$x_A$$ be the number of outer perimeter segments that $$A$$'s region touches, and the same for $$x_B$$ with $$B$$.

No matter how the game is played, $$s_A-s_B=x_A-x_B$$.

This is because in $$s_A-s_B$$, all interior segments cancel out.

Therefore, all that matters is grabbing up the outside perimeter segments. The best strategy is to claim a corner if possible, claim an edge square otherwise, and then play arbitrarily once the outer squares are all gone. $$A$$ and $$B$$ will each claim two corners and six edge squares, and therefore tie.