Question

Problem 4. (20 points) Pebbles Game. Two players play a game, starting with three piles of n pebbles each. Players alternate turns. On each turn, a player may do one of the following: take one pebble from any pile take two pebbles each from two different piles The player who takes the last pebble(s) wins the game. Write an algorithm that, given n, determines whether the first player can "force" a win. That is, can the first player choose moves such that, regardless of what the other player does, they will always win. In addition, write a procedure that tells a player which move (if any) they should make to force a win given the current triple of pebbles in each pile. What is the complexity of your solution?

Answer 1

Given: The information provided is given as follows:

• A game of pebbles is played by two players with each player having three piles of n number of pebbles each.
• The players play their game in an alternate manner.
• When the turn of any of the two player comes, one of the following two things can be done by the player:

• Pick one pebble from any of the pile.
• Pick two pebbles each from any two different piles.

• The player who picks the last pebble wins the game.

Aim: To design an algorithm such that the first player should choose his moves in such a way that no matter what moves the second player chooses, the first player will always win.

Note: It is given that each piles have n number of pebbles and there are 3 piles.

Therefore, total number of pebbles, N = 3n

Algorithm: The algorithm is given as follows:

1. While (total number of pebbles > 0)
2. do
3. If it is the turn of second player, it can choose any one of the methods to pick the pebbles.
4. If it is the turn of the first player, it has to pick the pebbles in such a way that the total number of pebbles left behind are in the multiples of 3.
5. The example given below can explain the concept:

$EGhMLffetewAAAAASUVORK5CYII=$

• In the above-mentioned figure, there are 3 piles with each pile having 3 pebbles.
• If the player 1 wants to force a win, it has to select the pick condition such that, the number of pebbles left behind when he picks should be in the multiples of 3.
• This will make sure that only three pebbles are left in last attempt for the second player and even if player 2 selects either of the two options, i.e., either 1 or 2 out of 3, the first player will still win.

Procedure defining which move will force a win:

• In order to force a win, the player should pick his option of choosing pebbles in such a way that the number of pebbles left behind after he chooses his option are in the multiples of 3.

Complexity:

• The complexity of the algorithm will be O(n) as ‘n’ number of iterations will be required in total.