From: Stefano Cirolini Newsgroups: rec.games.abstract Subject: Re: Number Games Date: 2 Jan 1996 11:00:56 GMT >Something I've seen that's sort of similar is > >Name: don't remember >Players: 2 >Equipment: paper and pen >Rules: Players alternate adding numbers between 1 and 10 inclusive to > a common total which starts out at 0. The player who makes the > total reach exactly 100 wins. >-- >Tom Barron | This sounds very like a NIM variant. An analysis and a winning strategy may be found in one of the Martin Gardner's books. -- Stefano Cirolini | "Considerate la vostra semenza: cirolini@sodalia.it | fatti non foste a viver come bruti, Sodalia SpA, Trento, Italy | ma per seguir virtute e canoscenza." phone +39-461-316-432 | (Dante Alighieri, Inferno XXVI) ============================================================================== From: Peter Chapman Newsgroups: sci.math Subject: Winning formula for NIM Date: Mon, 29 Sep 1997 11:49:31 +0800 I'm sure you're all familiar with the game of Nim, but for those of you who aren't: A number of items (often matches) are places in three piles. Players take turns in removing any or all of the matches in any one pile. The player who takes the last match loses. After playing a few games you quickly realize that there are certain losing combinations. 1-0-0 is an obvious losing combination, as are 1-1-1, 2-2-0, 3-2-1, 3-3-0, 4-4-0, 5-4-1, 5-5-0, 6-4-2 and 7-5-2. So, if it is your turn and you have 7, 5, and 2 matches then after your turn your opponent, with correct play, can always reduce what's left into another losing combination, and thus force a win. Is there a formula or method for determining whether a combination is a losing combination? What if the number of piles of matches is not limited to three? A pretty broad question I know but I figure that this maths is probably fairly well known by now (just not by me). advTHANKSance, Chappy. ============================================================================== From: Richard H Gould Newsgroups: sci.math Subject: Re: Winning formula for NIM Date: Tue, 7 Oct 1997 13:25:22 +0100 In article <342F254B.2179@info.curtin.edu.au>, Peter Chapman writes >Is there a formula or method for determining whether a combination is a >losing combination? If the objective is to pick up the last match, the winning strategy involves making the number of each power of 2 even (ignoring zero), if you are able to do so. Also the game is not restricted to 3 piles. So, suppose that you have: 10 (=8+2) 7 (=4+2+1) 5 (=4+1) 3 (=2+1) You have 1x8, 2x4, 3x2 and 3x1. Removing 9 from the pile of 10 will leave you with 2x4, 2x2 and 4x1. Any move your opponent now makes will leave an odd number of at least one power of 2 and, ultimately, this will be the last match. I imagine (but haven't proved) that, with the reverse objective, you would apply this (now losing) strategy, but leave one extra match at each stage. -- Richard H Gould |"Your feeble skills are no match| rhgould@gocomp.demon.co.uk |for the dark side of The Force" | ============================================================================== From: cet1@cus.cam.ac.uk (Chris Thompson) Newsgroups: sci.math Subject: Re: Winning formula for NIM Date: 7 Oct 1997 16:59:54 GMT In article , Richard H Gould writes: |> In article <342F254B.2179@info.curtin.edu.au>, Peter Chapman al.lastname@info.curtin.edu.au> writes |> >Is there a formula or method for determining whether a combination is a |> >losing combination? |> |> If the objective is to pick up the last match, the winning strategy |> involves making the number of each power of 2 even (ignoring zero), if |> you are able to do so. Also the game is not restricted to 3 piles. So, |> suppose that you have: |> |> 10 (=8+2) |> 7 (=4+2+1) |> 5 (=4+1) |> 3 (=2+1) |> |> You have 1x8, 2x4, 3x2 and 3x1. Removing 9 from the pile of 10 will |> leave you with 2x4, 2x2 and 4x1. Any move your opponent now makes will |> leave an odd number of at least one power of 2 and, ultimately, this |> will be the last match. I imagine (but haven't proved) that, with the |> reverse objective, you would apply this (now losing) strategy, but leave |> one extra match at each stage. The winning strategy for Misere Nim (last player loses) is actually: play exactly as in Normal Nim (last player wins, described above) until you are about to reduce the last pile with >=2 matches to 1 or 0 matches. Then reduce it to whichever of 0 or 1 you woudn't have done in Normal Nim; i.e. leave an odd number of single-match piles rather than an even number. All moves are clearly forced (up to isomorphism) after this. In general, misere play in impartial games is much more difficult to analyse than normal play, but there is a class of "tame" games in which the winning strategy is a simple modification of that in normal play. In this context, Nim is the tamest of tame games. Read "Winning Ways" (Berlekamp, Conway, Guy), and change your life... :-) Incidentally, Misere Nim was the form of Nim originally described by Charles Bouton in 1902. Chris Thompson Email: cet1@cam.ac.uk ============================================================================== Related links: http://www.cs.uidaho.edu/~casey931/conway/games.html http://www.awesomelibrary.org/Office/Main/New_and_Exciting/Games.html http://www.2020tech.com/fruit/tech.html http://www.cut-the-knot.com/nim_st.html http://www.maths.nottingham.ac.uk/personal/anw/Research/Hack/