3
$\begingroup$

Two players set several piles of chips. The piles are arranged in a row from left to right. By turns each player takes one chip from one of the piles and adds at will as many chips as he/she wishes (can be none) to any piles placed to the left of the pile from which the chip was taken. Assuming that the game ever finishes, the player that takes the last chip wins.

  1. Obviously (if there are initially at least two piles) a player can make the duration of the game arbitrarily long by taking a chip from the rightmost pile and adding a large enough number of chips to the left of it, but prove that, no matter how they play, the game will eventually end after finitely many steps.

  2. Find a winning strategy.

  3. Next, assume that instead of one row of piles we have several rows of piles (not necessarily with the same number of piles each). Let $(m,n)$ denote the position of the $n$-th pile of row $m$. By turns each player takes one chip from one of the piles, say the one in position $(m,n)$, and then adds as many chips as he/she wishes (can be none) to any piles in positions $(m',n')$, where either $m'<m$, or $m'=m$ and $n'<n$. Additionally the player can add any number of piles with any number of chips each to rows $1,\dots,m-1$. Prove that also in this case the game always ends in finitely many steps, and find a winning strategy.

  4. Generalize the problem to multi-dimensional arrangements of piles (and solve it) - the idea would be to have the piles represented with tuples of positive integers $(n_1,\dots,n_d)$, each with $N(n_1,\dots,n_d)$ chips, where $N(n_1,\dots,n_d) = 0$ for all but finitely many tuples. Each player picks a tuple $(n_1,\dots,n_d)$ such that $N(n_1,\dots,n_d) > 0$, takes one chip from it, and adds as many chips as he/she wishes (can be none) to piles placed at positions $(n'_1,\dots,n'_d) <_{\text{lex}} (n_1,\dots,n_d)$, where $<_{\text{lex}}$ is the (strict) lexicographical order in $(\mathbb{Z}^+)^d$. Again, prove that the game always finishes, and find a winning strategy.

$\endgroup$
  • $\begingroup$ Hi, welcome to Puzzling. Is this a homework question? $\endgroup$ – ABcDexter Dec 26 '18 at 19:22
  • $\begingroup$ Hello mlerma, nice to see you on Puzzling! If this isn't a homework problem but is found somewhere else, please quote the source! $\endgroup$ – TheSimpliFire Dec 26 '18 at 19:27
  • $\begingroup$ I have a vague memory of a game involving multiplications and divisions of integers that I read years ago and whose reference unfortunately I cannot remember. The exponents of the prime factors for the numbers behaved like the number of chips in the piles described at the beginning of this problem. At that time I thought the problem was better posed as a variation of nim. The multidimensional version (parts 3 and 4) as long as I can tell is mine, I never saw it posed by anybody else. $\endgroup$ – mlerma54 Dec 26 '18 at 20:14
  • 1
    $\begingroup$ By the way, this is one of various problems I was planning to pose in the "Math Challenges" site. I have a few more, some may fit here, others may go to "Math." $\endgroup$ – mlerma54 Dec 26 '18 at 20:31
4
$\begingroup$

1. Proof that all games will end after a finite number of steps

Proof by induction:

Induction hypothesis H: (not known to be true yet) All games of exactly N piles will end in a finite number of steps.

Induction step: If H is true for some N, it is also true for N+1. This is because out of the N+1 piles, one is the rightmost one. When a chip is removed from the rightmost pile, there can be at most "a game with N piles" worth of moves in between, before another chip will have to be removed from the rightmost pile again. There's a finite number of chips in the rightmost pile, and by H, the game with N piles ends in a finite number of moves, so a game with N+1 moves will also end in a finite number of moves.

Base case: H is true, if N equals 1. In this case, there will never be any chips added anywhere, so the game will end as soon as all the chips are taken.

Because H(1) is true, and because from H(N) we can deduce H(N+1), we have proven by induction that

For any integer N, a game with N stacks will end in a finite number of moves.

2. Winning strategy

As with most Nim variants, a good way to find the winning strategy is to start at the end of the game, and classify the positions into winning and losing ones.

Trivially, when there's only one chip, the position is winning. Similarly, a position with 2 chips is losing. In a similar manner, all positions with only one pile and an odd number of chips are winning, and all positions with only one pile and an even number of chips are losing.

Therefore, getting the last piece in the next-to-last pile is winning: you can choose the parity for the leftmost pile when you take that piece.

Also, since you can always leave an even number of chips on the leftmost pile(s), it doesn't really matter if the opponent wants to empty the left side before taking from the right again; you can always copy your opponent's pick and adjust any odd-sized piles to even-sized, and in the end, any emptying out of the left side will have taken an even number of moves, which means that the game eventually reduces to the single-pile version, played on the rightmost stack, with (possibly) some inconsequential moves in between.

Therefore, on your move, you can win if (and only if)

there is an odd number of chips in one or more of the piles.

and the optimal winning move is to always

take a chip from the rightmost odd-sized pile, and add a chip to all the other odd-sized ones, leaving only even-sized piles for your opponent.

3. Two-dimensional case

We proved in the one-dimensional case that the game is finite for any N. Therefore, we don't really care how many piles there are to the left (the additional piles appearing during the game will only lengthen the game by a finite number of moves).

Because we can ignore the additional piles, we can just line up all the piles in a single row, in order of significance (row 2 goes to the right of row 1, etc) thereby reducing the case into a previously solved one. There can be an arbitrarily long game on arbitrarily many piles in between, but eventually, yet another chip will have to be taken from the "most significant", rightmost pile.

The winning strategy remains the same.

4. Multidimensional case

See answer to question 3.

$\endgroup$
  • $\begingroup$ Well, the one-dimensional case shows that the game is finite for every fix $N$, but in the two-dimensional case the number of piles is variable. However the induction process can indeed be extended to the new dimension. The base case would be having one row. Then the induction step would go from $M$ rows to $M+1$. And the same reasoning can be performed with any new dimension added. The winning strategy would be the same. $\endgroup$ – mlerma54 Dec 27 '18 at 1:42
  • $\begingroup$ There is an alternative argument (to prove that the game is finite) consisting of mapping each configuration to an ordinal number in such way that after each move the new configuration maps to an ordinal that is less than the previous one. In the one-dimensional case having $N$ piles with $k_1,\dots, k_N$ chips each would map to the ordinal (in Cantor Normal Form) $\omega^{N-1} \times k_N + \omega^{N-2} \times k_{N-1} + \cdots + k_1$. The two-dimensional case would involve also ordinals of the form $\omega^{\omega^n}$, and so on. $\endgroup$ – mlerma54 Dec 27 '18 at 1:56
  • $\begingroup$ This sort of "move to any earlier ordinal" game has been studied by J H Conway; if you like this stuff and aren't already familiar with his lovely book "On numbers and games" then you might want to check it out. I think the most relevant chapter would be the one called "The curious field On2". $\endgroup$ – Gareth McCaughan Dec 27 '18 at 2:52
  • $\begingroup$ Beautiful book indeed. Another instance of proof using ordinals is that of Goodstein's theorem - en.wikipedia.org/wiki/Goodstein%27s_theorem $\endgroup$ – mlerma54 Dec 27 '18 at 5:24

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.