# Thread: Nim Variation

1. ## Nim Variation

One of my math professors came up with a variation on Nim (Nim - Wikipedia, the free encyclopedia) that our math club has been puzzling over for a while. Any ideas?

Take some number of coins, and arrange them on a table in piles. Two players, taking turns. A turn consists of removing some number of coins from any pile or piles, with one restriction: you must remove the same number of coins from each pile you take any from. The goal is to remove the final coin or coins.

2. Originally Posted by Black Carrot
One of my math professors came up with a variation on Nim (Nim - Wikipedia, the free encyclopedia) that our math club has been puzzling over for a while. Any ideas?

Take some number of coins, and arrange them on a table in piles. Two players, taking turns. A turn consists of removing some number of coins from any pile or piles, with one restriction: you must remove the same number of coins from each pile you take any from. The goal is to remove the final coin or coins.
Is the goal to have a guaranteed strategy for winning this game no matter who the opponent or how the piles are arranged? If so, there probably can be no guaranteed strategy for this. (I believe the solution would necessarily depend on how the piles are set up and may also depend on the opponent and/or on who is first to move).

I'm not sure exactly what your question/request is, but without a specific example, I doubt you'll get an answer.

3. Well, the goal is to win, of course. From any given arrangment of piles, either the player moving first has a way to guarantee a win, or their opponent does - that can be proven pretty straightforwardly by just regressing backwards through the game tree. The question is, is there any pattern to these strategies? That is, is there some general, efficient way of finding the best move possible from a given arrangement? In the case of ordinary Nim, there is a very simple strategy that will guarantee success starting from any arrangement where that's possible. There's also a complete solution to Wythoff's Game, which is a special case of Wim. I'd like to know if there's a similarly general winning strategy, or even a heuristic, that applies to this variation.

I'm not sure what you want, by way of a specific example, but I guess you're asking me to run through the game once. So, let's say the number of coins in each pile is represented by a number, with those numbers in a list: {2,3,8,6,5,1}. I don't know off the top of my head who's got the lead here, but I could write a program to run thorugh each possible game path from this starting position and determine a winning strategy for either the first person to move or the second person to move, whoever it is that has the advantage. Let's say I take three coins from the second, third, and fifth piles each. Then we have {2,0,5,6,2,1}. Maybe my opponent takes one from each pile remaining, leaving {1,0,4,5,1,0}. I recognize this, since I've simulated all games of about this size, and take five from the fourth pile: {1,0,4,0,1,0}. From here, my opponent has no viable options. No matter what he takes, I can respond, and I will definitely win. Say he takes two from the third pile. {1,0,2,0,1,0}. I take 1 from the first, reducing it again to a position from which he cannot win: {0,0,2,0,1,0}. He takes perhaps one from the third pile {0,0,1,0,1,0}, and I take everything that remains {0,0,0,0,0,0} to win the game.

In the case of Nim, as the article I linked in my original post describes, there's a structure to the game that can be taken advantage of. If you break the number describing each pile down in binary, and run the XOR operation on all piles interpreted bitwise, you get another binary number that either equals zero, in which case you'd better hope your opponent makes a mistake, or is nonzero, in which case it can be used to determine the ideal move. In Wythoff's Game, there's similar tricks involving either the Fibonacci numbers or the golden ratio. In the case of Wim where no pile has more than two coins in it, it is again completely solved. Ideally, I'd like to know a trick like that to solve the entire game, but anything anyone knows on the subject would be helpful.