Let $\mathcal{F}$ be a finite family of subsets of some set $X{}$. It is known that for any two elements $x,y\in X$ there exists a permutation $\pi$ of the set $X$ such that $\pi(x)=y$, and for any $A\in\mathcal{F}$ \[\pi(A):=\{\pi(a):a\in A\}\in\mathcal{F}.\]A bear and crocodile play a game. At a move, a player paints one or more elements of the set $X$ in his own color: brown for the bear, green for the crocodile. The first player to fully paint one of the sets in $\mathcal{F}$ in his own color loses. If this does not happen and all the elements of $X$ have been painted, it is a draw. The bear goes first. Prove that he doesn't have a winning strategy.
Problem
Source: Russian TST 2018, Day 4 P2
Tags: combinatorics, set theory, game, TST, Russian TST, Game Theory
R8kt
08.05.2023 13:53
Bump bump
R8kt
08.05.2023 14:05
Would be nice if it was possible to prove that there exist a composition of permutations which sends a big set S1 to S2 with them being disjoint.
math90
09.05.2023 00:27
Should $X$ be finite?
R8kt
09.05.2023 00:31
F being finite with the permutation condition implies X being finite.
R8kt
02.06.2023 22:54
Bumpbump
dgrozev
06.06.2023 12:13
Assume on the contrary, the bear wins by painting at his first move a set $ Y\subset X.$ Of course, $ Y\neq X.$ Note that for any $ x\in X, x\not \in Y,$ the bear also wins by painting at his first move some set $ Y'\subset X, |Y'|=|Y|, x\in Y'.$ Indeed, take any $ y\in Y$ and consider a permutation $ \sigma, \sigma (y)=x$ that satisfies the condition of the statement. Then, the bear also wins by painting at his first move the set $ Y':= \sigma(Y).$ This can be shown by the following symmetry argument. Imagine that there are two bears that play on two different copies of $ X.$ The original (winning) bear plays on the first board and starts by painting $Y$ brown. The second bear paints $Y'=\sigma(Y)$ brown and waits for the crocodile's move. After the crocodile responds with painting, say, a set $Z',$ the second bear passes to the first bear the set $Z:=\sigma^{-1}(Z')$ painted green. The first bear paints $Y_1,$ according to his strategy. The second bear then paints $Y'_1:=\sigma(Y_1)$ and so on. So, now the bear with his winning strategy paints at first $ Y.$ The crocodile makes the following calculation in his mind. Assume, he knows the bear's strategy and he, as if he were the bear, starts by painting $ Y'$ green. Suppose the bear (as the crocodile) responds by painting the set $ Y\setminus Y'$ brown. The crocodile (as the bear) must win and let his winning move in this situation be to paint (green) some set $ Y_1.$ Now, the crocodile acts. He paints in his first move the set $ (Y'\setminus Y)\cup Y_1$ green. Then he follows the bear's winning strategy and wins because the only difference is that $ Y'\cap Y$ is painted brown, instead of green, but if he wins when $ Y'\cap Y$ is painted green, he will also win in this situation. Contradiction!
dgrozev
09.06.2023 14:30
The method used is called strategy-stealing argument. I commented on some other examples, including this problem, on my blog. Interestingly, if painting only one element per move was allowed, you cannot apply the same trick. Although, it's intuitively worse for a player to paint more than one element. But in case the family contains a set of two elements, this is still true, as shown in the given link.