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 left, and it is Fred’s turn. What move should Fred make to guarantee himself victory? (Hint: Use your answer to part (a) and roll back.)
(c) Now start from the beginning of the game. If both players play optimally, who will win?
(d) What are the optimal strategies (complete plans of action) for each player?

Hope your writing looks readable and please draw the tree if possible.

Solutions

Expert Solution

Ans A)

The one who removes last stick wins and we can remove either 1,2 or 3 sticks therefore if 5 sticks are left then Fred should remove only 1 matchstick which will be left with only 4 matchsticks to choose for Barney in next round.

Barney can maximum choose 3 sticks then Fred will move final stick to win the game; If Barney removes 2 sticks then too Fred will win the game by removing 2 sticks ; If Barney removes 1 stick then too Fred will win by removing 3 sticks

hence Fred should remove only 1 stick when 5 sticks are left.

Ans B)

If 10 match sticks are left then Fred should remove 2 matchsticks so that 8 will be left

Now if Barney removes 3 matchsticks then 5 are left and we can follow part A)

If Barney removes 2 matchsticks then 6 are left and Fred can move 2 more match sticks which are left with 4 sticks to remove for Barney but Barney at most can remove 3 match sticks and hence Fred will win.

If Barney removes 1 matchstick then 7 are left and Fred can move 3 more match sticks which are left with 5 sticks to remove for Barney but Barney at most can remove 3 match sticks and hence Fred will win.

Ans C) & D)

The player who starts the game should always win if and only if he start the game by choosing 1 matchstick.

Game Plan as below

Now assume Fred starts the game and removes 1 matchstick therefore in 2nd round Barney can at most remove 3 matchsticks. The Game plan is Fred should make these sticks removal and they are 5th, 9th, 13th,17th.

In 2nd round when Barney removes any sticks between 1 to 3 then in 3rd round Fred will remove only up to 5th stick.

In 4th round Barney removes any sticks between 1 to 3 then in 4th round Fred will remove sticks up to 9th stick

similarly in the 10th round Barney is left with only 4 sticks and he can not remove more than 3 sticks and this game would be won by Fred in 11th round by removing 21st stick

Rahul Sunny answered 1 year ago

Next > < Previous

Related Solutions

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...

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.

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?

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 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?

1. Consider the following game. There are two piles of matches and two players. The game...

1. Consider the following game. There are two piles of matches and two players. The game starts with Player 1 and thereafter the players take turns. When it is a player's turn, she can remove any number of matches from either pile. Each player is required to remove some number of matches if either pile has matches remaining, and can only remove matches from one pile at a time. Whichever player removes the last match wins the game. Winning gives...

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...

Consider the following game, which might model the “Split-or-Steal” game show. Two players simultaneously choose whether...

Consider the following game, which might model the “Split-or-Steal” game show. Two players simultaneously choose whether to split or steal. If they each choose to split, they each get $50. If one chooses steal and the other chooses split, then the stealer gets $100 and the splitter gets $0. If both choose steal, they each get $0. (a) Assume the players care both about their own monetary earnings and the amount of inequality between their earnings: for a pair of...

Consider a following zero-sum game of two players a) Reduce the initial game to a 2x2...

Consider a following zero-sum game of two players a) Reduce the initial game to a 2x2 game. Eliminate only strictly dominated strategies. In the obtained 2x2 game name Player 1’s (Row player’s) strategies “Up” and “Down” and Player 2’s (Column player’s) strategies “Left” and “Right”. b) Find all Nash equilibria of the 2x2 game (both in pure and mixed strategies) ALL ANSWERS MUST BE EXPLAINED. 2 0 1 -1 1 0 1 2 3 1 2 0

Consider a following zero-sum game of two players a) Reduce the initial game to a 2x2...

Subjects