0
$\begingroup$

Consider the following two-player game:

The game begins with k tokens placed at the number 0 on the integer number line spanning [0,n].

Each round,one player, called the chooser, selects two disjoint and nonempty sets of tokens A and B. (The sets A and B need not cover all the remaining tokens; they only need to be disjoint.) The second player, called the remover, takes all the tokens from one of the sets off the board. The tokens from the other set all move up one space on the number line from their current position.

The chooser wins if any token ever reaches n. The remover wins if the chooser finishes with one token that has not reached n.

1) If k>= 2^n , how can I find a winning strategy for the chooser?

2) If k< 2^n , how can I prove with a probabilitic method that a winning strategy for the remover exists ?

3) How can I use the method of conditional expectations to derandomize the winning strategy for the remover when k < 2^n ?

$\endgroup$
2
  • $\begingroup$ What have you tried so far? What are your thoughts about how to start solving the problem? $\endgroup$ May 21 '17 at 10:09
  • $\begingroup$ Well , about 1) , my strategy is the following : I divide all tokens into two equal sized groups . Half of them are eliminated after step 1 , the other half advance to the next square. Then I repeat the same strategy.Half of them are eliminated , half advance . Finally, one token makes it to the last square . I am still thinking about 2) and 3) though... $\endgroup$
    – user448194
    May 21 '17 at 10:16
1
$\begingroup$

1) The chooser can guarantee that after $r$ rounds ($r\le n$), at least $2^{n-r}$ tokens are on field $r$ (in particular, there is at least one token on field $n$ after $n$ rounds). This is clear for $r=0$. For the induction step $r\to r+1$ (with $r<n$), the chooser partitions the $\ge 2^{n-r}$ tokens on field $r$ into two sets of size at least $2^{n-r-1}$ each. Then the remover will push these to field $r+1$.

2) Let the remover simply toss a coin to decide which of the to sets to remove. A token ending up on field $n$ must have been in the "lucky" subset $n$ times (an never in the "unlucky" subset). The expected number of tokens with such a streak of luck is at most $2^{-n}k$, so less than one. We conclude that a deterministic strategy can also enforce less than one, i.e., no token on field $n$.

3) Say that the "value" of a situation with $a_i$ tokens on field $i$ is $\sum 2^ia_i$. If we remove $A$ and advance $B$, we get rid of the value of $A$ and double the value of $B$. It follows that removing the more valuable of the sets $A,B$ cannot increase the total value. Thus when starting from an initial value of $k<2^n$, the remover can avoid that the value ever grows to $2^n$ or more.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.