4
$\begingroup$

I want to solve this problem:

Let there be $n \ge 2$ points around a circle. Alice and Bob play a game on the circle. They take moves in turn with Alice beginning. At each move:

  • Alice takes one point that has not been colored before and colors it red.

  • Bob takes one point that has not been colored before and colors it blue.

When all $n$ points have been colored:

  • Alice finds the maximum number of consecutive red points on the circle and call this $R$.

  • Bob finds the maximum number of consecutive blue points on the circle and call this $B$.

If $R \gt B$, Alice wins. If $B \gt R$, Bob wins. If $R = B$, no one wins. Does any of the players have a winning strategy?

We still seem not to know for which odd $n$ Alice has a winning strategy. She does for $n=3$, and it seems also for $n=5$. But in general, I'm not sure. Could someone help?

$\endgroup$
1
  • 1
    $\begingroup$ For $n \in \{1, 3, 5\}$ Alice is guaranteed to win no matter how the game is played. For $n \in \{2, 4, 6\}$ a draw is guaranteed no matter how the game is played. For $n = 7$ I found a winning strategy for Alice, but a draw is possible if Alice makes a mistake. For even $n$ there are different ways for Bob to force a draw. But I still don't have a general solution for odd $n$, which is what you are really asking about. $\endgroup$ – kasperd Apr 21 '18 at 19:31
5
$\begingroup$

For even $n$, Bob can force a tie, as follows. Divide the circle in half in any way, and then mirror Alice's moves on the other side.

For example, $1-2-3-4-5-6-7-8(-1)$ can be split into $1-2-3-4-$ and $5-6-7-8-$. Then $1$ is mirrored to $5$, $2$ to $6$, $3$ to $7$, and $4$ to $8$. Initially, all pairs are vacant; every time Alice moves into one element of a pair, Bob moves into the other. If Alice moves into $1$, Bob moves into $5$, etc. At the end of the game, the two haves will be opposite, so Bob's longest consecutive string is equal to Alice's.

In particular, this means that Alice cannot force a win.

$\endgroup$
1
  • 2
    $\begingroup$ What about odd $n$? $\endgroup$ – user547757 Apr 21 '18 at 16:36
1
$\begingroup$

For even $n$, we can see that Alice can force a tie in a similar way to how @vadim123 shows that Bob can force a tie:

She divides the circle in half in any way (not necessarily the same way as Bob would).

She starts by picking any point (it does not matter which).

Then, for every move Bob makes, she looks at the opposite point, which is either

  1. Empty, in which case she should play that point.
  2. Not empty. By construction, it would be her point. She can again pick a random point.

By above's algorithm, Alice is guaranteed to have an exact mirror of Bob's points. Hence: a tie.

This shows that neither Alice nor Bob can have a winning strategy (for even $n$).

$\endgroup$
3
  • $\begingroup$ I don't see any reason to divide the circle in two. All you need to know which points are opposite and play accordingly (whether you are Alice or Bob). $\endgroup$ – Joonas Ilmavirta Apr 21 '18 at 21:45
  • $\begingroup$ It's worth noting that this forces Bob's last move (since Bob does get last move) to also be at a mirror of Alice's point. $\endgroup$ – Steven Stadnicki Apr 21 '18 at 21:54
  • $\begingroup$ @StevenStadnicki It would force Bob's last move to mirror one of Alice' points, not necessarily the last one Alice played. $\endgroup$ – kasperd Apr 21 '18 at 22:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy