Register

TIFR CSE 2017 | Part A | Question: 14

• edited by
2,898 views
9 votes
9 votes

Consider the following game with two players, Aditi and Bharat. There are $n$ tokens in a bag. The two players know $n$, and take turns removing tokens from the bag. In each turn, a player can either remove one token or two tokens. The player that removes the last token from the bag loses. Assume that Aditi always goes first. Further, we say that a player has a winning strategy if she or he can win the game, no matter what other player does. Which of the following statements is TRUE?

  1. For $n=3$, Bharath has a winning strategy. For $n=4$, Aditi has a winning strategy.
  2. For $n=7$, Bharath has a winning strategy. For $n=8$, Aditi has a winning strategy.
  3. For both $n=3$ and $n=4$, Aditi has a winning strategy.
  4. For both $n=7$ and $n=8$, Bharat has a winning strategy.
  5. Bharat never has a winning strategy.
• edited by
User Avatar

4 Answers

Best answer
16 votes
16 votes

Point to be noted- 

1. Always Aditi starts the game.
2. A player loses the game if he/she has to remove the last item.
3. A player always removes 1 or 2 items with a winning strategy.

Method 1:  shortcut- time complexity-  O(1)         

           n = total no of tokens.

      If  n mod 3 - 1 = 0, then Bharat has a winning strategy (1 is the last token being taken by the loser)

       if n mod 3 - 1 = 1 or 2, then Aditi has a winning strategy. 

The trick here is with 4 tokens whoever plays next is not having a winning strategy. So, the strategy must be to ensure that the opponent always takes his turn with $3n+1$ tokens. This is possible because if the opponent takes 1, I take 2 and vice verse.

Let's check each option- 
[Here my strategy of solving this would be just contradicting the each option by considering all the possibilities].

A. For n =3. // Here I am trying to make Bharat win, Let's see if he can win or not.
     Aditi -   removes 2 item , n = 3-2 = 1
     Now only 1 item remains, so Bharat is forced to remove the last item and loses the game. Hence for n=3, Aditi has a winning strategy. 
The first part of A - False.

    For n =4. //  Here I am trying to make Aditi win, Let's see if she can win or not.
     Case -1:                                                                             case 2:
     Aditi -   removes 1 item , n = 4-1 = 3    Aditi -   removes 2 item , n = 4-2 = 1
     Bharat- removes 2,item , n = 3 -2 =1    Bharat- removes 1,item , n = 2 -1 =1
     Now only 1 item remains in both the case, so Aditi is forced to remove the last item and loses the game. Hence for n=4, Bharat has a winning strategy.
The 2nd part of A - True.

Hence, A- False.

B. For n =7. // Here I am trying to make Aditi win, Let's see if she can win or not.
    Case 1:                                                                        Case 2:
 Aditi -   removes 1 item , n = 7- 1 = 6           Aditi -   removes 2 item , n = 7- 2 = 5
 Bharat- removes 2 item , n = 6 -2 = 4.          Bharat- removes 1 item , n = 5 -1 = 4.

Now remaining tokens in both the case, n = 4.


case 1:                                                      case 2:  

Aditi - removes 1 item ,n=4-1 = 3          Aditi -   removes 2 item , n = 4-2= 2.

Bharat- removes 2,item ,n=3-2=1,         Bharat- removes 1,item , n = 2-1 =1.


Now in both the case, only 1 item remains, so Aditi is forced to remove the last item and loses the game. Hence for n=7, Bharat has a winning strategy. Aditi could not win the game even taking all possibility of Aditi's turn.

  For n = 8. // Here I am trying to make Aditi win taking all possibility of Bharat's turn, Let's see if she can win or not.


     Aditi -   removes 1 item , remaining item n = 8 - 1 = 7
     Case 1:                                                   case 2:

Bharat-  removes 1 item , n = 7 - 1 = 6.      Bharat-  removes 2 item ,n = 7 - 2 = 5.

Aditi -    removes 2 item , n = 6 - 2 = 4   ,    Aditi -   removes 1 item , n = 5-1 = 4.

Now In both cases, remaining items = 4.
            case 1                                                     case 2  
Bharat- removes 1,item ,  n = 4-1 = 3          Bharat- removes 2,item , n = 4-2 = 2.
Aditi -   removes 2 item , n = 3-2 = 1   ,        Aditi -   removes 1 item , n = 2-1 = 1.


Now in both the case, only 1 item is remaining so Bharat is forced to remove the last item and loses the game. Hence for n=8, Aditi has a winning strategy.

B- True.

C. For both n=3 and n=4, Aditi has a winning strategy. 

  See explanation for A. where Bharat has a winning strategy for both n=3 and n=4.

 Hence, False.

D. For both n=7 and n=8, Bharat has a winning strategy.

See explanation for B. where Aditi has a winning strategy for both n=8.

 Hence, False.

E. Bharat never has a winning strategy.

   See explanation for B where Aditi has a winning strategy for both n=8.

  Hence, False.

Ans - B.

• edited by
User Avatar
8 votes
8 votes

Let's assume we have $n$ coins and two players $A$ and $B$

Rule of the game:

  • Both will pick some coins one at a time
  • They can pick exactly 1 or X or Y coins at a time.
  • A starts the game
  • One who picks at the end, loses.
  • And the other one wins.


Starting few games both play casually. After some time both realizes that for some particular values of $n$,
There are some sequence of moves for a player such that he will definitely win that instance of the game, irrespective of the other player's moves.That means for a particular value of $n$ we can predict the outcome of an instance of a game assuming that A and B play optimally. (how they will play optimally, because they gained experience by playing many such instance and we can leverage computer program to compute the result of a game, without playing even single move! awesome !)


Let's us define some important terms that will be helpful in describing the algorithm

Player = Who make the first move in a game instance with $n$ coins.
Game State = It has two parameters 
No of coins ($n$) and the Player
Result or Result of a game with $n$ coins = $0$ if Player loses and $1$ if Player wins

We start a new Game State with $n$ = $10$ and Player = $A$ and Assume we (as well as $A$ and $B$) know somehow all game results with $n$ values smaller than $10$. (just assume for time being).
Assume X = $2$ and $Y$ = $3$

Now,
A has $3$ options

  • pick $1$ coin
  • pick $2$ coins

or

  • pick $3$ coins

This is how $A$ Thinks

  • If I pick $1$ coin, remaining is $9$, I know the result of game($9$)
  • If I pick $2$ coins, remaining is $8$, I know the result of game($8$) also
  • and If I pick $3$ coins, remaining is $7$, I know the result of game($7$) too.

$A$ recollects that game($9$) result was $1$. That means the one who makes the first move in a game instance with $9$ coins, that person definitely wins. $A$ also knows, after him $B$ will start and from game($9$) result, $B$ will definitely end up winning game($10$), this current game !!! $A$ is not going to allow this to happen.

  • So $A$ forgets about picking $1$ coin.
  • $A$ thinking about picking $2$ coins ....


$A$ recollects that game($8$) result was $0$. That means the one who makes the first move in a game instance with $8$ coins, that person definitely loses. $A$ also knows, after him, $B$ will start and from game($8$) result $B$ will definitely end up losing game($10$), A smiled !! A is happy now !. A will pick two coins and we know + $A$ knows game($10$) will definitely end up in favor of A.

$A$ may or may not think about picking $3$ coins (no need at all)....

  • This whole idea can be easily implemented by bottom-up dynamic programming, becomes easier than top_down recursion.

Code explanation: (bottom up)

  • game is an array tracking the results of each game with parameter $n$ = no of coins.
  • we develop the game array from lower indices i.e. form $0$. That means we calculate what is game[0] first, then game[1], then game[2]..etc.. and so on.
  • One weird point : game[0] = 1 always. 
  • How ? as follows:

If there is only one coin. and the $Player$ is $A$. $A$ have to pick that coin and after that in front of $B$, what is left? NOTHING empty. And $B$ wins.
We define winning definition as follows :

  • If A player is about to play a move and he finds empty then he wins.

So by this intuition game[0] = 1.

bottom up code :

// Debashish Deka Dec/26
#include <iostream>
#include <stdio.h>
#define N 1000
const int X = 2;
const int Y = 2;

bool game[N];

int main() {
	int n;
	scanf("%d",&n);
	game[0] = true;
	for(int n_c = 1 ; n_c <= n; n_c++) {
		
		// each iteration is a game with initial coins = n_c 
		// first assume that player will lose
		// player = who goes first for any instance of this game
		game[n_c] = false;
		
		// player checks for taking 1
		// if status of remaining_coins game is false
		// then player will win this instance of game !!
		if(!game[n_c-1]) game[n_c] = true;


		// player checks for taking X
		// if status of remaining_coins game is false
		// then player will win this instance of game !!

		if(n_c >= X && !game[n_c - X]) game[n_c] = true;

		// same logic..

		if(n_c >= Y && !game[n_c - Y]) game[n_c] = true;
	}

	if(game[n]) 
		printf("A\n");
	else 
		printf("B\n");
}

Top down code with memoization:

// Debashish Deka Dec/26
#include <iostream>
#include <stdio.h>
#define N 1000
const int X = 2;
const int Y = 2;
int cache[1000];
int game(int);
int main() {
	int n;
	scanf("%d",&n);
	for(int i=0;i<=n;i++) {
		cache[i] = -1;
	}
	cache[0] = 1;
	if(game(n) == 1) {
		printf("A\n");
	}else {
		printf("B\n");
	}
	return 0;
}

int game(int n_c) {
	if(cache[n_c] != -1) {
		return cache[n_c];
	}
	int p = 1,q = 1,r = 1;
	if(n_c >=1) p = game(n_c-1);
	if(n_c >=X) q = game(n_c-X); 
	if(n_c >=Y) r = game(n_c-Y);

	if( !(p && q && r)) {
		return 1;
	}else {
		return 0;
	}
}

We can manually count up to game[7] or game[8] Option B

the manual calculation is shown below:


 

• edited by
User Avatar
2 votes
2 votes
For n=4 no matter what aditi do bharat will win the game. Hence, bharat has winning strategy for n=4. From these conclusions you can eliminate options a,c,e. Hence either b or d is correct. b and d both claim that Bharat has winning strategy at n=7. Hence, it can be concluded that bharat has winning strategy at n=7.
Hence, for n=7 the person who moves second wins the game. Now, for n=8 aditi if picks one token can transform the game into n=7 with bharat being the first player and aditi herself being second.
Hence, for n=8 aditi will always win the game starting from picking one token.
Option b is correct.
User Avatar
0 votes
0 votes

This game is commonly known as subtraction game which is a variant of nim game of combinatorial game theory and since here, player who removes last token, loses the game. So it is played as misere game.  For a single bag/pile/heap, it follows a pattern.

Assuming both players play optimally and no player do the mistake.

Aditi = $A$ and Bharat = $B$

$X - N$ means player X removes N tokens from the bag.

For $n=1,$ $A$ - $1$, So, $B$ wins

For $n=2,$ $A$ - $1$, $B$ - $1$. So, $A$ wins

For $n=3,$ $A$ - $2,$ $B$ - $1$. So, $A$ wins 

For $n=4,$ If $A$ chooses either $1$ or $2$, she leaves $3$ or $2$ tokens. Now, as from the previous cases , in case of $n_l=3$ or $n_l=2$, person who play first win the game. Since, here, Bhart's move, So, he always wins either A started with $1$ token or $2$ token. So, here, $B$ wins.

For $n=5$, Similar reasoning as previous. $A$ chooses either $1$ or $2$, she leaves $n_l=4$ or $n_l=3$. Since, for $n_l=4,$ player who plays $2^{nd}$ wins the game, since it is Bhart's move, So, aditi will win. For, $n_l=3$, who play 1st wins, $B$ wins. So, for $n_l=4 $, $A$ wins. Hence, for $n=5$, Aditi has a winning strategy if she removes initially $1$ token. 

Similarly,

For, $n=6$, $A$ wins

For, $n=7$, $B$ wins

For, $n=8$, $A$ wins

So, there is a pattern here, for $n=4,7,10,13,16,...$ i.e. for $n=3k+1$, $k=0,1,2,3,...$, Bharat has a winning strategy. So, for all other values of $n$ aditi will have the winning strategy. It can be proved using induction.

If there are $2$ players Player $1$ and Player $2$ and there are $n$ tokens/coins/stones in a bag/pile/heap and each player can remove tokens from $1$ to $m$ and if player $1$ started the game and player who removes last loses the game then player $2$ will always have winning strategy if $n=(m+1)k+1$ where, $k=0,1,2,3,....$ 

Similar Queston.

User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

Link Copied!