# On Wythoff's game of Nim

I have heard about this informatics problem and I am sure that it is in fact a math problem and I have no idea if it was solved before or not, but I am sure that it is something known about the sequences that answers the question (I have heard the answer from a college that had found this interesting rule but had no idea why it works). The problem (it is from a romanian site) sounds like this:

"Macarie and Petronela play a very exciting game that, they hope, will develop even more their intelligence. So they have two piles of stones (with $A$ and $B$ stones each). The game runs alternately (Macarie begins), and at some point a player can take a number of stones from a pile or get the same number of stones from both piles. The one who can not take stones anymore lose."

The problem is to find the winner with $(A, B)$ given (we consider for simplicity that $A \leq B$). After some examples we find that the second player wins in the following situations : $(1, 2)$, $(3, 5)$, $(4, 7)$, $(6, 10)$ etc. My college found this rule: "starting from $1$ and with the difference 1, we search every integer positive number that it wasn't used and we add the difference and obtain a pair. After that we continue searching for numbers and after every step the difference raises with $1$".

So starting with $1$ and difference $1$ we find $(1, 2)$. Next we search the first unused numbers. $2$ was used before so we find $3$ and by adding difference now $2$ we obtain $(3, 5)$ and so on. In the problem we have that $1 \leq A, B ≤ 1.000.000$ so my friend just found all these pairs in which the second player wins(in every other case the first player wins) and sent the problem and took 100 points, so it was correct. Now I find these sequences very interesting : $1, 3, 4, 6, ...$ and respectively $2, 5, 7, 10, ...$. Of course that if we find the rule for one sequence, the same is for the other. But I can't find any rule and I also think that we have to consider both of the sequences to find something.

I was thrilled by this problem because it looks that it's something very complex, hiding maybe something else. Do you have any idea of these sequences? It is something known?

• This is equivalent to a problem covered by singingbanana on YT :), maybe you want to take a look. However others may give you a proper answer with more detail, whats going on here. Link to the problem on YT: youtube.com/watch?v=pzlpi7lJi4k – Imago Nov 11 '17 at 9:17
• Look up Wythoff's game. – bof Nov 11 '17 at 9:22