2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Here's where things start getting interesting.

circle game

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?

enter image description here

$\endgroup$
  • $\begingroup$ Thanks for your answer! So, I'm guessing there's no way, given $n$, its side length, and $r$, to determine what type of Nim game this becomes? In your second example $r$ was large enough where it was obvious, but if $r$ is much smaller than a side length, it seems a lot more complicated and maybe I don't immediately see how it turns into Nim. $\endgroup$ – anonymouse Mar 7 '16 at 14:47
  • $\begingroup$ I've added a new picture. $\endgroup$ – Ed Pegg Mar 7 '16 at 17:07
  • $\begingroup$ The image helps a bit. I don't quite understand your notation: "red region (1 or 3)." It does turn into an equivalent of multi-group Nim, which I believe is solved for all cases (correct me if I'm wrong). I'm just wondering how to take an empty triangle and a fixed $r$ and determine what the best starting move is for Alice. Maybe I'll read up on combinatorial game theory. (: $\endgroup$ – anonymouse Mar 7 '16 at 17:13
  • $\begingroup$ Either 1 or 3 coins can be played in the red region. If 2 are played, there will be space for a third. The regions are developed by the moves of the players. An easier game is domineering, which is still unsolved for the 11x11 board. This circles game has non-discrete moves, so it will become combinatorially intractable at some size. $\endgroup$ – Ed Pegg Mar 7 '16 at 17:32
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ We implicitly assume that Alice can make a first move. So what happens in the case of odd $n$ when $r << r_0$? In addition, how can I formalize my argument for even $n$? It seems like a mess of words right now with no coherent progression. $\endgroup$ – anonymouse Mar 4 '16 at 20:38
  • $\begingroup$ I would guess that for any particular $n$ and $r$, it is possible in principle to solve the game by looking at a finite set of cases. However, if $r$ is small it will be hellishly complicated. $\endgroup$ – Robert Israel Mar 4 '16 at 20:43
  • $\begingroup$ What I considered for $n = 3$ was drawing the three altitudes to split the triangle into six equipartitioned regions. The problem is that you can place circles along partition lines. I think there might be some clever way to reduce the case of odd $n$ to the case of even $n$, but my altitude method didn't work. I'm also not a very good geometrist, for what it's worth, so I can't see how to proceed with partitioning my triangle. $\endgroup$ – anonymouse Mar 4 '16 at 20:45
  • $\begingroup$ As for formalizing the case of even $n$, you show by induction on the number of moves that Alice can always produce a position that is symmetric under rotation by $\pi$. $\endgroup$ – Robert Israel Mar 4 '16 at 20:47

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.