Browse · MathNet
PrintBaltic Way 2019
Baltic Way 2019 counting and probability
Problem
Let be a finite set with elements. Two players, and , alternately choose nonempty proper subsets of , where
(1) it is not allowed to choose a set that contains a set previously chosen by any player,
(2) it is not allowed to choose a set that is contained in any previously chosen set,
(3) it is not allowed to choose a set whose union with any previously chosen set is .
begins. The player who first cannot choose a set anymore loses. Which player has a winning strategy?
(1) it is not allowed to choose a set that contains a set previously chosen by any player,
(2) it is not allowed to choose a set that is contained in any previously chosen set,
(3) it is not allowed to choose a set whose union with any previously chosen set is .
begins. The player who first cannot choose a set anymore loses. Which player has a winning strategy?
Solution
It is straightforward to verify that the following is a winning strategy for . Player first chooses a singleton subset . After that, he responds to choosing a set by choosing .
Final answer
Player A has a winning strategy.
Techniques
Games / greedy algorithms