Black and white play sequentially the game $S_{n,k}$ with $k,n\in \mathbb N \space 0\leq k\leq n$
the game board consists of all subsets $A\subseteq\{1,2,...,n\}$ such that $1\leq |A|\leq k$.
every player in it's turn chooses a subset from the board and eliminates it and all the subsets containing it. the winner is the one that eliminates the last subset. white starts and the players aware of the game's state all the time.
for example assume the game is $S_{3,2}$. choosing $\{1\}$ will eliminate $\{1\},\{1,2\},\{1,3\}$.
prove that if $n=k$ then white has a winning strategy.
Does anyone know the name of the game?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ I assume that $\emptyset$ isn't allowed since the player who takes the empty set wins immediatly. $\endgroup$– DannyNov 11, 2014 at 20:02
-
$\begingroup$ @Danny: It says so: $1\le|A|\le k$. $\endgroup$– Brian M. ScottNov 11, 2014 at 20:03
-
$\begingroup$ Ah, okay. Sorry. $\endgroup$– DannyNov 11, 2014 at 20:03
-
$\begingroup$ $0 \leq k$ and $1 \leq |A| \leq k$, excluded. $\endgroup$– TacetNov 11, 2014 at 21:24
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
"Strategy stealing" should work here. If choosing $\{1,2,\dots,n\}$ is a winning first move for White, fine. If not, Black's winning response to $\{1,2,\dots,n\}$ is a winning first move for White.
$\begingroup$
$\endgroup$
Your subject line and your problem contradict each other (do you want black or white to win?), but I think a simple strategy-stealing argument works here -- if the second player has a winning strategy, then the first player can just take $\{1, \ldots, n\}$ and then pretend to be the second player, yielding a contradiction.
answered Nov 11, 2014 at 20:10