Pow 16

Linear Nim

Problem Statement:

The game of Linear Nim is a strategy game in which two players take turns removing or eliminating lines or bars from a series of ten lines or bars. There are ten bars or lines in a row on a piece of paper:

l l l l l l l l l l

Each player takes a turn and crosses off one, two, or three of the lines until all of the lines have been crossed off; the person who crosses off the last mark wins.

The question I was trying to answer in this POW is, what is the best strategy for winning this game, i.e. is there one strategy that if followed, will assure that I win the game every time I play it? To decide this, I needed to consider such things as does it matter if one goes first or second to win, and does it matter how many lines get marked off on the first turn, will these make a difference in winning?

To answer the question, the tasks that I needed to do were to play the game several times to see if I noticed any patterns, to write out all of the ways I think might work to help one win, to test those strategies by playing the game again & using them, and then to develop my final strategy and do some variations of it to make sure that my winning strategy truly always works.

Process and Solution:

To answer this question, the first thing I did was to play this game several times with family and friends, looking to see if I noticed any patterns or if I could predict who would win. I started recording the numbers being crossed off and at first it seemed pretty random and puzzling. It didn't seem to matter who went first or how many were marked off on the first turn, but I doubted it was that random or just a matter of luck. After a few more games, I had an "ah-ha" moment: I noticed that if on your turn you made sure that there were four lines left for your opponent, then you were guaranteed to win. I saw that with 4 lines remaining:

If my opponent marked off 1, then three were left for me=I win;

If my opponent marked off 2, then two were left for me=I win;

If my opponent marked off 3, that left 1 for me=I win.

I was pretty excited about that observation and played the game several more times to test it out. I always won when I could get to the point of there being 4 lines remaining when it was my opponents turn. The second challenge, however, was how to make sure I could always get it to where there were 4 remaining and not 5 or 6, for example, when it was my turn so I had to play it several more times before I saw the answer, that if I went first and marked off two, then I was always guaranteed to win, that under this way there was no chance for my opponent to win.

Strategies:

The winning strategy that I came up with then was to go first and to always scratch off two. This meant that 8 were left and 8 follows the same pattern as the 4 above, i.e.

if they marked 3 that left 5 so I would do one and that left four=I win;

if they marked 2 that left 6 so I would do 2 and that left four=I win;

if they marked 1, that left 7 so I would do 3 and that left four=I win!

The obvious formula then was their number plus mine must always equal four (3+1, 2+2,1+3) and if you start with 2 then you always have a group of 8 or 4 that you can control the outcome of by applying this system to. No matter what their choice, to eliminate one, two, or three, if I follow the above and make sure that their number plus mine always leaves four and then they can't win and I always will. Yeah!

The strategy is complete because I tested it with every possible number variation and it always came out right with me winning; and this strategy is successful because no other outcomes are possible when you follow this strategy.

Variations:

I decided to try two variations of this game and see what would happen. The first variation was to have 20 lines or marks and to allow opponents to mark off one, two, three, or four lines at