Waste less time on Facebook — follow Brilliant.
×

Deterministic Games

Whether you’re just playing around or a master of games, see how mathematical and logical ideas can be combined to analyze games from tic-tac-toe to Nim.

Nim (Step Up Quiz)

         

This is a series called Step Up which goes through a five-step process of problem solving. Our ultimate goal is to find a winning strategy for the game below.

Two-pile Nim: There are two piles of coins. On each turn a player can draw any number of coins from one particular pile (but not both piles at once). The person who takes the last coin wins. It's your turn. The first pile has 30 coins and the second pile has 25 coins.


Step 1: Analyze the description of the game and to understand the rules.

Which of these first moves will allow your opponent to win on their immediate next move? (It may be none of these are winning strategies, but the question is to identify the one that loses quickest.)

Two-pile Nim: There are two piles of coins. On each turn a player can draw any number of coins from one particular pile (but not both piles at once). The person who takes the last coin wins. It's your turn. The first pile has 30 coins and the second pile has 25 coins.


Step 2: Next, explore different possibilities. It's often easier to work with simpler cases and organize the results; here our cases will be possible situations in the game. We're going to keep track of our possibilities with a table.

Suppose the first pile has only one coin and the second pile has only one coin.

If a particular game situation results in a win for you (supposing it is what you see before you move), put a "W" for win, otherwise an "L" for loss. Which of these tables is correct?

Two-pile Nim: There are two piles of coins. On each turn a player can draw any number of coins from one particular pile (but not both piles at once). The person who takes the last coin wins. It's your turn. The first pile has 30 coins and the second pile has 25 coins.


Step 3: Continue filling in the table. (Remember, if a particular case results in a win for you, put a "W" for win, otherwise an "L" for loss.) Theorize about any patterns that you see; it can make the process go faster.

Which of these is correct for the first row of the table?

Two-pile Nim: There are two piles of coins. On each turn a player can draw any number of coins from one particular pile (but not both piles at once). The person who takes the last coin wins. It's your turn. The first pile has 30 coins and the second pile has 25 coins.


Step 4: Continue filling in the table. Remember you fill in a W if the situation wins for you and an L if the situation loses for you. You want to give your opponent losing situations. (That is, change the pile so when it is your opponent's turn they are looking at an L on the chart.) Also, remember you already should have the first row of this table now!

After you've collected enough cases, formulate a winning strategy. What is it?

Two-pile Nim: There are two piles of coins. On each turn a player can draw any number of coins from one particular pile (but not both piles at once). The person who takes the last coin wins. It's your turn. The first pile has 30 coins and the second pile has 25 coins.


Step 5: Time to answer the final question: how many coins should you take at your first move to win?

×

Problem Loading...

Note Loading...

Set Loading...