Placing circles inside of a regular polygon.

Question

Alice and Bob play the following game: on a table there is a regular $n$-gon. On each person's turn, they are required to place a circle of radius $r$ fully in the interior of the $n$-gon such that it does not overlap with any previously placed circles. If they cannot place a circle on their turn, they lose. For what values of $n$ does Alice or Bob have a winning strategy, assuming Alice goes first, and what is the strategy?

---

To give some context, I've never taken a game theory course before, so right off the bat I don't know how to "prove" anything here. Any help would be appreciated, and if my work so far is correct, some notion on how to formalize it and make it presentable would be fantastic.

I conjecture that for even $n$, Alice has a winning strategy.

On her first turn Alice will place a circle whose center coincides with the center of the $n$-gon. Alice will continue her turns as follows: when Bob places a circle, Alice will place a circle such that the center of the $n$-gon is the midpoint between Bob's circle's center and Alice's circle's center.

I argue that Alice will always have a circle to play. Let's say that Bob makes a move such that Alice cannot conduct her strategy. This would mean that previously some of the space occupied by Alice's would-be move was taken up. However, given Alice's strategy, this would mean some of the space occupied by Bob's winning move was also taken up, meaning Bob's winning move is nonexistent.

This strategy does not work for odd $n$ because reflecting across the center of the $n$-gon may put you outside of the interior region. I'm not sure if Bob has a winning strategy in this case. Because it is not necessarily advantageous to place one's first move in the center of the $n$-gon, Alice's first move can be anywhere. And I can't make a pretty WLOG statement about how the game progresses after her first move.

Answer 1

Your argument for even $n$ is correct, assuming of course that $r < r_0$, where $r_0$ is the inradius of the $n$-gon.

For any $n$, if $r$ is close enough to $r_0$, Alice will win by placing her first circle at the centre, as Bob will have no possible first move. On the other hand, if $r \ge r_0$, Alice loses by having no possible first move.

Answer 2

Here's where things start getting interesting.

In this triangle, a play at the center is a loss for Alice. That would create three playable areas that do not interact. Bob wins.

Playing higher in the triangle creates two playable regions that do not interact.

This would be a combinatorial game for some boards. Each move would have the possibility of increasing the number of playable areas, which may or may not be able to affect each other. Once the various regions can't interact, then the game can be played like Nim. You'd want to leave a favorable nim-sum.

Here's a more complicated game after five moves -- the black disks. There are four well defined regions that cannot affect each other now, a red region (1 or 3), Cyan (2, 3, 5), Blue (1 or 3), Green (1). There is also a larger region remaining. Does Bob have a winning move at this point?