Browse · MathNet
PrintBaltic Way 2019
Baltic Way 2019 counting and probability
Problem
The two women Inger and Ellen play the following game. On a large piece of paper are six-pointed snowflakes , placed in general position (and not touching). Each of the six arms of the snowflake has an extreme end, called its apex.
A move consists of drawing a curve connecting two apices, possibly belonging to the same snowflake. The curve may not intersect itself and may not touch any previously drawn curves. Also, it may not touch any of the snowflakes (except at the two apices forming its endpoints). Each apex may be used only once.
Inger makes the first move, and then the players alternate. The first player who cannot make a move has lost the game. Which player has a winning strategy?
A move consists of drawing a curve connecting two apices, possibly belonging to the same snowflake. The curve may not intersect itself and may not touch any previously drawn curves. Also, it may not touch any of the snowflakes (except at the two apices forming its endpoints). Each apex may be used only once.
Inger makes the first move, and then the players alternate. The first player who cannot make a move has lost the game. Which player has a winning strategy?
Solution
Inger has a winning strategy.
Let Inger select an arbitrary snowflake and connect a pair of opposite apices. By the Jordan Curve Theorem, this curve (along with ) will divide the plane into two domains, the curve (along with ) being their common boundary. It is obvious that Inger may draw her curve in such a way that exactly snowflakes fall in each domain. Each successive move must then be made entirely within one of these two domains. Since the two domains are combinatorially identical (though possibly not geometrically), Inger may respond to each move of Ellen in one domain by the corresponding move in the other, and will win the game.
Let Inger select an arbitrary snowflake and connect a pair of opposite apices. By the Jordan Curve Theorem, this curve (along with ) will divide the plane into two domains, the curve (along with ) being their common boundary. It is obvious that Inger may draw her curve in such a way that exactly snowflakes fall in each domain. Each successive move must then be made entirely within one of these two domains. Since the two domains are combinatorially identical (though possibly not geometrically), Inger may respond to each move of Ellen in one domain by the corresponding move in the other, and will win the game.
Final answer
Inger has a winning strategy.
Techniques
Games / greedy algorithmsCombinatorial Geometry