In the regular version of the game Nim, you have $n$ piles of stones, and you may remove one or more stones from a single pile in your turn. A modification I thought of involves the concept of piles that may contain not just stones, but also other piles. Let's call these "super-piles". Similarly, we may have "super-super-piles" – piles that may contain stones, piles, or super-piles. In general, a "$k$-pile" may contain stones, and/or $i$-piles for any $1\leq i<k$.

Now, in your turn, you may choose any $k$-pile, and remove all of its contents. Note that this $k$-pile may either be the outermost one, being contained in no bigger pile, or else it may be one of the contents of a $(k+1)$-pile. As in regular Nim, the person with no possible move loses.

Is this version of Nim known? Does it have a name? I've tried looking it up on the internet and in popular Game Theory textbooks, but I've had no luck. If this has not been worked upon previously, Can this game be solved using the Sprague–Grundy theorem? In simpler words, given the starting state of the game, can you predict whether the first player would win or the second one, assuming both players play optimally?

  • 2
    $\begingroup$ Obviously, you can design your game however you want and the question is still completely valid. But this isn't the generalization of Nim that I was expecting. We can say that a stone is a $0$-pile and, in ordinary Nim, we're given a collection of $1$-piles. But we can't play ordinary Nim with your rules: the only moves allowed under your rules are to either remove a $0$-pile (a stone) or a $1$-pile (a whole Nim pile). Don't you instead want the rule to be that you pick a $k$-pile and remove any subset of its contents? $\endgroup$ – David Richerby Oct 1 '17 at 12:11
  • 1
    $\begingroup$ This seems to be Hackenbush on trees? $\endgroup$ – Hendrik Jan Oct 1 '17 at 14:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.