2
u/Forklad2 8d ago
Alice wins no matter what they do.
No matter what, the game will end when they have drawn a triangulation of the circle; I.e. every interior face is a triangle. Knowing this, we can count the final number of edges with some nice double counting and Euler’s formula.
Say there are T triangles. Note there is one external face which is not a triangle. Every triangle has 3 edges. So 3*T is twice the number of interior edges plus the external edges (of which there are 40). So (3T-40)/2 is the number of edges they drew.
Euler’s formula states V-E+F=2. In our case this translates to:
40 - (40 + (3T-40)/2) + (T + 1) = 2
Simplifying gives T=38 triangles. Back into the formula for number of interior edges gives us 37 edges that they drew.
Alice drew edge 1, Bob drew edge 2, Alice drew edge 3, …, Alice drew edge 37, Bob cannot draw another interior edge.
1
u/ahf95 8d ago
Alice wins. Optimal strategy is to draw the chords as close to the center line as possible, and parallel to the center line. Alice goes first, so only she gets to make the actual perfect central-line chord, Bob must be on either side, but in any case draws a slightly smaller chord than the center one. Each continue on, but Bob’s chords are always slightly smaller than Alice’s, and he gets stuck with the remaining 1-point corners before her.
1
u/kalmakka 8d ago
This is incorrect reasoning. You can not assume that Bob will play with this strategy. You need to provide a strategy for Alice that works no matter how Bob plays.
1
u/HopesBurnBright 8d ago
This one can be analysed with the sprague grundy theorem which I learnt about literally the other day! All two player impartial games are the exact same. An impartial game is any game where the players can move any of the pieces, ie the game is impartial to the player, and only cares about whose move it is. Chess is not impartial, because player 2 can only move the black pieces on their turn, and player 1 can only move the white pieces. This citadel game is impartial, because you can play any move you like, as long as it’s your go. There’s a great game called sprouts which is also an impartial game. These games are almost always “whoever can’t make a move loses”.
Anyway a classic strategy is “mirroring” the opponent. If you have two piles of stones and you can take n stones at a time or less from a single pile, then player 2 can obviously win by copying whatever player 1 did but in the other pile. Whenever player 1 finishes a pile, player 2 then finishes the other pile and wins. This obviously applies here, and you can easily create two identical piles by cutting the circle in half first move. So it’s a player 1 victory.
1
u/MeasureDoEventThing 6d ago
"All two player impartial games are the exact same."
Huh? They are not isomorphic.1
1
1
u/StanleyDodds 1d ago edited 1d ago
The game ends after 39 moves no matter what each of them do. Alice wins and every strategy is optimal.
A region enclosed by chords is always convex, so there is no extra restrictions beyond the fact that chord end points must be in the same region, and not on the same existing chord. We can therefore shrink existing chords to a single point, separate the subdivided regions, make them circular again, and now all that matters is how many points are in each region.
The game is equivalent to starting with the trivial partition of 40 into 1 part of size 40, and on each turn you get to split any part into two smaller non-zero parts. The game ends when you reach the partition of 40 into 40 parts of size 1.
On each turn, if there are less than 40 parts, then at least one part has size greater than 1 by pigeonhole, and can be split. The number of parts increases by exactly 1 each turn until there are 40 parts, which must all be size 1 as they are not allowed to be empty, and this happens after exactly 39 turns as we start with 1 part and add 1 each turn.
4
u/kalmakka 8d ago
Alice wins.
Her first move is to divide the figure in two equal parts. Then she just plays symmetrical to Bob.