2
$\begingroup$

A two-player game begins with $k<2^n$ tokens placed at point $0$ on the number line spanning $[0,n]$. Each round, player $A$ chooses two disjoint, non-empty sets of tokens $X,Y$. Player $B$ takes all the tokens from one set off the board, while the tokens from the other set all move up one space on the number line. $A$ wins if some token ever reaches $n$, while $B$ wins if $A$ finishes with one token that hasn't reached $n$. Use the probabilistic method to show that $B$ can win.

I came up with this algorithm for $B$ to win:

Define the potential function $\Phi = \sum_{i=1}^k2^{r_i}$, where $r_i$ is the current position of token $i$. The potential function starts at $k<2^n$. It suffices for $B$ to not increase the potential with each step, because then $A$ will not reach his goal of having potential at least $2^n$. To accomplish this, $B$ throws away, each step, the set with greater potential function. Then if the contribution from the two sets was $x+y$, with $x<y$, it is now $2x$, which is no more than $x+y$. So $B$'s strategy works.

Still, I'm curious about how to use the probabilistic method to show that $B$ must have a winning strategy. How would it work?

$\endgroup$

1 Answer 1

2
$\begingroup$

Suppose that $A$ plays some strategy $\sigma$, while at each turn $B$ flips a fair coin to choose which of the piles to remove. Then at each turn the probability that a given token still on the board will advance is at most $\frac12$, with equality only when $\{X,Y\}$ is a partition of the tokens still on the board. The probability that a given one of the original $k$ tokens will advance $n$ times is at most $\left(\frac12\right)^n$, so the expected number of tokens reaching $n$ is at most $\frac{k}{2^n}<1$. Since the number of tokens reaching $n$ is an integer, this at least shows that $\sigma$ is not a winning strategy: there is at least one outcome in which $B$ wins, and that sequence of choices for $B$ constitutes a winning counterstrategy to $\sigma$. Since $\sigma$ was arbitrary, $B$ has a winning counterstrategy against every possible strategy for $A$, and therefore $B$ has a winning strategy.

$\endgroup$
2
  • $\begingroup$ Beautiful! Note that this also gives rise to the potential function algorithm I described -- at each step $B$ "chooses the flip of the coin" that does not increase the expected number of tokens reaching $n$. $\endgroup$
    – simmons
    Nov 5, 2014 at 19:18
  • 1
    $\begingroup$ @simmons: I really like the potential function algorithm: not only is it clear why it works, it’s actually easy to use in practice! $\endgroup$ Nov 5, 2014 at 19:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .