Skip to main content
OlympiadHQ

Browse · MathNet

Print

Baltic 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?
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