on a game playable with tokens

Question

Here is a two-player game playable with tokens. At the beginning, all tokens form a single heap. Players must choose among all heaps one of them and cut it in two parts, so that all heaps have distinct numbers of tokens. Here is an example with 12 tokens : 12 -> (7;5) -> (5;4;3) -> (5;4;2;1) and player 2 loses as he doesn't have a legal move.

I think that trying to determinate whether the initial position with N tokens is a win for player 1 or 2 is difficult, but maybe there are some values of N for which there is an effective strategy. Do you know if this game is known and if it is possible to find a study on the net ? Also, there is an optional rule when you have to cut always the heap with the greatest number of tokens, but even if it reduces the number of possible moves, I am not sure this will help in finding some strategy for particular numbers.

Comments are welcome! :)

Answer 1

joriki's comment is right on the money. Let $m$ be $\left\lfloor \dfrac{\sqrt{8N+1}-1}{2} \right\rfloor$ (so that $m$ is greatest such that the $m$-th triangular number is not greater than $N$). A heap with $N$ tokens is a first player win exactly when $m$ is even.

Why? After $m-1$ moves, there will be $m$ heaps, and by the choice of $m$, there can't possibly be any more moves available. It remains to show that $m-1$ moves are always possible. But this follows by counting the number of ways to split the largest heap, and comparing that with the current number of heaps: they can't all be blocked (again by choice of $m$).

---

As an aside, if you had said "cut it in two parts, so that those two parts have distinct numbers of tokens", then the game is the very famous Grundy's game, which has proven difficult to analyze for arbitrarily large heaps.