ZIO07002 - Editorial

Problem Link: https://www.iarcs.org.in/inoi/2007/zio2007/zio2007-qpaper.pdf

PREREQUISITES: Basic Logic.

Explanation:

Understanding the problem:

  1. The game is played by two players and there are two piles of coins, each of them may have a different number of coins.
  2. Player 1 will always have his first turn and Player 2 will always have his second turn and it continues alternatively.
  3. The rule of the game is that in each move, a player can either remove one coin from one of the piles or one coin from both piles.
  4. The player who picks the last coin loses the game.

Some Conclusions:

  • Since the moves in the game are played alternatively, the one who gets the first turn (here Player 1) will always win, if and only if he plays intelligently and either one of the piles has an odd number of coins.

  • The one who plays the second turn (here Player 2) will always win, if and only if he plays intelligently and both plies have an even number of coins.

Note: At the initial stage, none of the piles will have 0 number of coins (only one pile) as it is mentioned in the question that there are two piles of coins in the beginning stage.

----------------------------------------------------Let me you show how---------------------------------------------------

Case 1: When the number of coins in one pile is an odd number.

Let’s say we have 3 (odd) coins in one of the piles and 2 (even) in another.

We know there are 2 ways to select coins at each stage i.e, either you can pick 1 coin from one of the piles or 1 coin from each of the piles but in either way Player, 1 will always win at the end if he plays intelligently. Notice at stage (1) the Player 1 must select 1 coin from the 1st pile in order to win, else he loses.

Case 2: When both piles have an even number of coins.

Let’s say we have 4 (even) coins in one of the piles and 2 (even) in another.

Again there are 2 ways to select coins at each stage i.e, either you can pick 1 coin from one of the piles or 1 coin from each of the piles but in either way Player, 2 will always win at the end. Notice at stage (2) the Player 2 must select 1 coin from the first pile in order to win, if he removes one coin from each pile or one coin from the 2^{nd} pile, at this stage, then the condition becomes favourable for Player 1 that is, 2 (even), 1 (odd) or 3 (odd), 1 (odd).

-------------------------------------------------Coming up with the Solutions---------------------------------------------

(a) Suppose we have 20 coins in one pile. In the other pile, Player 1 is allowed to choose the number of coins to start with. He has to pick a number greater than or equal to 16. With this restriction, what is the smallest value for which Player 1 is guaranteed to win the game?

Given: Number of coins in one pile = 20 coins.

To Find: Number of coins needs to be in another pile?

Solution: Let the number of coins be X.

According to question, X must be the smallest number greater than or equal to 16. Now we know, for Player 1, either one of the piles must have an odd number of coins.

There are 20 (even) coins in 1 pile already so we need to add an odd number of coins to another pile to make the conditions favourable for Player 1. 17 is the required number which is the smallest odd number greater than equal to 16.

X = 17

(b) Suppose we have 32 coins in one pile. In the other pile, Player 2 is allowed to choose the number of coins to start with. He has to pick a number less than or equal to 51. With this restriction, what is the largest value for which Player 2 is guaranteed to win the game?

Given: Number of coins in one pile = 32 coins.

To Find: Number of coins needs to be in another pile?

Solution: Let the number of coins be X.

According to question, X must be the greatest number less than or equal to 51. We know, for Player 2, the number of coins in both piles must be even.

There are 32 (even) coins in 1 pile already so we need to add an even number of coins to another pile to make the conditions favourable for Player 2. 50 is the required number of coins which is the greatest even number less than or equal to 51

X = 50

( c ) Suppose we have 26 coins in one pile. In the other pile, Player 1 is allowed to choose the number of coins to start with. He has to pick a number greater than or equal to 15 and less than or equal to 25. Among these, for how many values is Player 1 is guaranteed to win the game?

Given: Number of coins in one pile = 26 coins.

To Find: How many different numbers of coins can be in another pile?

Solution: Let the number of different values of coins be X.

According to question, X must be greater than or equal to 15 and less than or equal to 25. We know, for Player 1, either one of the piles must have an odd number of coins.

There are 26 (even) coins in 1 pile already so we need to add an odd number of coins to another pile to make the conditions favourable for Player 1. 15, 17, 19, 21, 23 and 25 can be the required odd number of coins which are greater than or equal to 15 and less than or equal to 25. So there are 6 different number of coins which satisfies all the criteria.

X = 6

Thanks!:smiley:

1 Like