Simple Nim game with equal-sized piles.

2,278

An even number of two coin piles is losing for the first player. As second player, just pair the piles up and what the first player does to any pile you do to its match. You can go through the two pile game first to give the idea.

Added: if you want to show strong induction, I would use the proposition that two equal-sized piles is a second player win. Base case is $(0,0)$, then if proved up to $(n,n)$ the first move from $(n+1,n+1)$ is to $(n+1,m)$ with $m \le n$ and the second player can move to $(m,m)$ which we know is a win. The problem with an even number of piles of $2$ for this purpose is you really have to prove for an even number of $2$'s plus and even number of $1$'s. This makes a two dimensional induction-for no piles of $2$ you have a win with no piles of $1$, with two piles of $1$, etc. Then you can induct on the (even) number of piles of $2$.

Share:
2,278

Related videos on Youtube

firemind
Author by

firemind

Updated on August 01, 2022

Comments

  • firemind
    firemind over 1 year

    Consider the standard Nim game, i.e. you can take as many coins as you want from a single pile, you should take at least one coin and you can't take coins from two or more different piles at the same time and last player to take a coin wins.

    I am looking for a proof of the following statement:

    Prove that if the number of piles are even and each pile contains two coins, the starting player loses.

    The proof should be targeting an audience of people without previous exposure to combinatorial game theory or the Nim game jargon (balanced position, Nim sums etc.), and knows basic game theory. In short it should be a proof using simple (or strong) induction, nothing else.

    Thanks.

    • firemind
      firemind over 11 years
      Note: The statement is true now, I accidentally typed odd instead of even.
    • Jyrki Lahtonen
      Jyrki Lahtonen over 11 years
      I have found that a description of the "Tweedledum-Tweedledee" approach to such positions of the NIM-game makes sense to a relatively general audience. I tried it out recently to an audience of mathematically talented junior high school freshmen. They were the finalists of a local math contest. I talked about NIM as a way of passing time, while my colleagues were busily grading their solutions.
  • firemind
    firemind over 11 years
    Yes, I typed wrong, I meant even. Sorry about that.
  • Henry
    Henry over 11 years
    After the edit to the question, this is still the answer, without the preliminary comment. The second player wins by matching the first player's moves.
  • firemind
    firemind over 11 years
    @Henry So should the strong induction proof should go like: (Inductive Hypothesis) Assume that for all numbers from n ranging from 1 to k, the second player can win the game of p=2n piles by matching the first player's move, then show that this is true for p=2(k+1)
  • Henry
    Henry over 11 years
    It is obvious, but you can use induction for the two pile case, and then induction on more piles: the second player can always either remove the remaining coins or move to a balanced position with fewer coins by matching moves and (by induction) a balanced position with fewer coins is a second player win.
  • firemind
    firemind over 11 years
    @Henry Thanks a lot. I don't think its obvious, even though I inducted my way up to 6 piles. Somehow my brain doesn't connect to the 2n case for arbitrary n. Though, I managed to come up with a proof that uses standard induction for the case of two coins on each pile (it took around 1.5 pages).
  • Ross Millikan
    Ross Millikan over 11 years
    @firemind: The pairing strategy allows you to handle any set of piles that can be divided into matching pairs, so $(1,1,2,2,3,3)$ as well as sets of two. Basically you convince yourself that $(n,n)$ is a second player win, then you just have a bunch of games like that.