In the subtraction game, two players start with a pile of chips and they alternate taking away any number (from a previously fixed set of positive integers) of chips from the pile. If you can’t make a move anymore, because there are less chips left than the smallest member of , you lose. This game has been solved in the case , but thus far hasn’t been solved in general when , although some partial results are known. For example, it is known that for any set there exists an such that for large enough , if you start with chips, the question if this game is a win for Player only depends on . That is, the sequence of such that Player wins if the starting pile consists of chips, is ultimately periodic. I think I found the period and the corresponding nimvalues (http://en.wikipedia.org/wiki/Nim-sequence) of the periodic parts, assuming . No explanation or anything, just stating what I think are the correct values. Maybe I’ll explain what the hell I’m talking about in a future post. Maybe not 😉

Let , where and . Then the periodic part of the nimsequence is as follows:

, if

– is odd

– is odd

, if

– is odd

– is even

Notice: thus far we’ve handled all cases with odd. This was known before, check for example http://arxiv.org/pdf/1202.2986.pdf.

, if

–

–

, if

– is even

–

, if

– is even

– is odd

–

Note: now we handled all cases with even and odd.

, if

– is even

–

Note: and now we’re also done with .

, if

– is even

–

–

, if

–

–

–

And now we’re also completely done with . All that’s left now is the case even and even, where if , . We will split this case in three: either exactly equals , or , or , and in this last case we have to distinguish between or . Here goes.

, if

– is even

– is even

–

, if

– is even

– is even

–

, if

– is even

–

–

–

– Using the fact that , these last two assumptions can be written as:

, if

– is even

– is even

–

### Like this:

Like Loading...

*Related*

This entry was posted on June 26, 2014 at 01:13 and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply