There are 21 pennies on a table between two players. The two players take turns removing...

There are 21 pennies on a table between two players. The two players take turns removing either 1, 2 or 3 pennies at a time. The player who takes the last penny loses. Use backward induction to come up with a strategy that the player who takes the second turn in the game can use to guarantee that she wins the game.

Solutions

Expert Solution

The strategy for player 2 is to remove 4 - number of pennies removed by player 1

By backward induction, player 2 can guarantee winning if he removes the 20th penny in his turn

He can guarantee removeing the 20th penny if he removes the 16th penny. This is because if he removes the 16th penny, the maximum player 1 can reach in 16+3 = 19th penny. Thus, for any choice of player 1, player 2 can always remove the 20th penny.

Following this reasoning, player 2 has to remove the 12th, 8th and the 4th penny (multiples of 4)

Thus, the strategy is if player 1 removes 1 penny, player 2 should remove 4-1 = 3 pennys

if player 1 removes 2 penny, player 2 should remove 4-2 = 2 pennys

if player 1 removes 3 penny, player 2 should remove 4-3 = 1 penny

Rahul Sunny answered 1 year ago

Next > < Previous

Related Solutions

Consider a game in which two players, Fred and Barney, take turns removing matchsticks from a...

Consider a game in which two players, Fred and Barney, take turns removing matchsticks from a pile. They start with 21 matchsticks, and Fred goes ﬁrst. On each turn, each player may remove either one, two, or three matchsticks. The player to remove the last matchstick wins the game. (a) Suppose there are only 5 matchsticks left, and it is Fred’s turn. What move should Fred make to guarantee himself victory? Explain your reasoning. (b) Suppose there are 10 matchsticks...

There are 100 coins in a jar. Two players take turns removing anywhere from 1-10 coins...

There are 100 coins in a jar. Two players take turns removing anywhere from 1-10 coins from the jar. The player who empties the jar by removing the remaining coin(s) wins the game. To guarantee that you win the game, would you choose to move first or second, and what strategy would you follow?

Two people are playing an exciting game in which they take turns removing marbles from a...

Two people are playing an exciting game in which they take turns removing marbles from a bag. At the beginning of the game, this bag contains some red marbles and some blue marbles. The bag is transparent so at any time during the game, the players know exactly how many red and how many blue marbles are in the bag. The players alternate taking turns. On a player’s turn, he or she must remove some marbles from the bag. The...

Two players take turns taking sticks from a pile of 16 sticks. Each player can take...

Two players take turns taking sticks from a pile of 16 sticks. Each player can take at most 3 sticks and at least 1 stick at each turn. Whoever takes the final stick wins the game. Describe in words the optimal strategy for each player. Is there a first-mover advantage in this game? Is there a second-mover advantage?

Suppose two players take turns playing another version of the parlor game discussed in class on...

Suppose two players take turns playing another version of the parlor game discussed in class on Tuesday. In this version, players can say any whole number between 1 and 10. The first person to get the running total to 25 wins. Do you want to go first or second? Figure out the optimal strategy for this game. Show your work. (b) (5 points) ECN-322 only for this part: Suppose two players take turns playing another version of the parlor game...

Two players, 1 and 2, take turns choosing numbers; 1 goes first. On his turn, a...

Two players, 1 and 2, take turns choosing numbers; 1 goes first. On his turn, a player may choose any number between 1 and 10, inclusive, and this number is added to a running total. When the running total of both players’ choices reaches 100, the game ends. The player whose choice of number takes the total to exactly 100 is the winner. (i) Who wins the game when we solve it using backwards induction? (ii) Provide a (not necessarily...

Stacking pennies to the moon Estimate how many pennies it would take to stack them from...

Stacking pennies to the moon Estimate how many pennies it would take to stack them from the earth to the moon. Give your answer in 1000s of dollars. How much would all of these pennies weigh? Give your answer in tons. Why did I ask you to estimate instead of giving an exact answer? Be sure to state your assumptions and define your estimations. Include justification for these. Use these facts (do not look up additional facts to help): Moon...

For Exercises explain how each experiment can be simulated by using random numbers. Two players match pennies.

For Exercises explain how each experiment can be simulated by using random numbers.Two players match pennies.

In this game, two players sit in front of a pile of 100 stones. They take...

In this game, two players sit in front of a pile of 100 stones. They take turns, each removing between 1 and 5 stones (assuming there are at least 5 stones left in the pile). The person who removes the last stone(s) wins. Write a program to play this game. This may seem tricky, so break it down into parts. Like many programs, we have to use nested loops (one loop inside another). In the outermost loop, we want to...

This is the full question Consider a‘‘duel’’ between two players. Let’s call these players H and...

This is the full question Consider a‘‘duel’’ between two players. Let’s call these players H and D.Now,we have historical information on each because this is not their first duel. H will kill at long range with probability 0.3 and at short range with probability 0.8. D will kill at long range with probability 0.4 and at short range with probability 0.6. Let’s consider a system that awards 10 points for a kill for each player. Build a payoff matrix by...

Subjects