1
$\begingroup$

I'm having problems finding an algorithm to the following problem:

A and B take turns replacing a number $n$ of tokens with either $floor((n+1)/2)$ or $n-1$. The player who makes one token remain wins. We want to know, if there is a way for B to win the game no matter the moves of A. A begins the game.

My idea is the following:

Is n = 1 -> No way for B to win the game

We try all moves of first A then B and check for 1 -> There is a way for B to win

But this does not incorporate the "no matter the moves of A" criteria.

$\endgroup$
2
$\begingroup$

I'd check what happens for some small(ish) values of initial $n$, working up. If you know who wins if there are at most $n$ on the table, working out what happens with $n + 1$ is easy.

$\endgroup$
  • $\begingroup$ I wrote down the trees for everything up to 8 (at which point the tree is very big) and the only valid candidate is still 3. I cannot find a particular pattern. $\endgroup$ – Bastian Hofmann Jan 28 at 17:15
  • 1
    $\begingroup$ @BastianHofmann, I suggest editing the question to show your progress so far. I'm not sure what is meant by "the only valid candidate is still 3". You might also consider what procedure you've been using to figure it out, and whether that's something that an algorithm could do. $\endgroup$ – D.W. Jan 28 at 17:39
  • $\begingroup$ @BastianHofmann, you really don't need the full tree. If you know the answers for all $n$ up to $N$, the answer for $N + 1$ is either the one for $N$ or $\lfloor (N + 2) / 2 \rfloor$, both of which you computed before. $\endgroup$ – vonbrand Jan 28 at 17:43

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.