Tackling Coin Picking Problems

hemant_malhotra
Director at ElitesGrid  CAT 2016  QA : 99.94, LRDI  99.70% / XAT 2017  QA : 99.975
How many coins should you pick in order to win When the person to pick the last coin is the loser or person to pick last coin is winner
#CASE 1
There are 105 coins on the table. You and your opponent take turns to pick 1 to 10 coins in each turn. How many coins should you pick in order to win
a) When the person to pick the last coin is the winner
b) When the person to pick the last coin is the loserApproach= let us understand that in any two consecutive turns, it is always possible to pick a total of 11 coins (we choose 11 because here 1 + 10 = 11)
if he picks 1, we can pick 10
if he picks 2, we can pick 9
if he picks 3, we can pick 8
.
if he picks 10, we can pick 1
We will use this for our benefit (ALWAYS )Now let us have a look at the two types of questions
TYPE I:
When the person to pick the last coin is the winner
Try to go backwards
If I want to win, I should be the last person to pick the coin
If in last turn 2nd guy has less than 10 coins, he would have won. but I don't want him to win! that means he had 11 coins in his last turn.
Now since we know that we can always maintain 11 coins in two turns, we can say that he had 22 coins in the previous turn.
and before that 33 coins
so he should have 11, 22, 33, 44, 55, 66, 77, 88, 99 coins
so we will pick 6 coins to win in this case
because 105  6 = 99"Short cut = n mod r"
where n=total coins
r = min + max coins that we can pick in this turn
in this case r= 1+10 = 11
n=105
so 105 mod 11 = 6Method2 (Best way to tackle):
Max =10, min =1 ,10+1=11..last player who picks winner ..hence leave the coins in the form of 11n always. no matter how many coins the opponent picks, he will always win in 11n, put n = 9 hence pick 6 coin and leave 99
Example= 17 coins now i picked 6 coins
so 11 coins are there so u picked 10 coins then i will pick 1 coin and will be the winnerEXAMPLE There are 25 coins on the table. You and your opponent take turns to pick 1 to 7 coins in each turn. How many coins should you pick in order to win, when the person to pick the last coin is the winner.
Approach
min = 1 and max = 7 and total = 8
so he will leave coin in form of 8k
so he will leave 24 coins and will pick 25  24 = 1 coin#TYPE 2
There are 105 coins on the table. You and your opponent take turns to pick 1 to 10 coins in each turn. How many coins should you pick in order to win, when the person to pick the last coin is the loser
Approach
When the person to pick the last coin is the loser
Again going backward,we want the other person to lose
so he should have 1 coin in his last turn(so that he is compelled to pick it)
Again since we can maintain a sum of 11 coins in two turns, we can say that he had 12 coins before that and 23 before that
,1, 12, 23, 34, 45, 56, 67, 78, 89, 100 coins should be left with him
And hence we have to pick 5 coins in this case to win
as 10  5 = 100Shortcut = (n1)mod r
where n=total number of coins
r = min + max number of coins that one can pick in each turn
Here (105  1) mod 11 = 5or Method2 (IMPORTANT)
Max =10, min =1 ,10 + 1 = 11..
last player who picks looses..hence leave the coins in the form of 11n + 1 always. No matter how many coins the opponent picks, he will always loose.....in 11n + 1, put n = 9 hence pick 5 coin and leave 100EXAMPLE There are 30 coins on the table. You and your opponent take turns to pick 1 to 7 coins in each turn. How many coins should you pick in order to win
a)When the person to pick the last coin is the winner
b)When the person to pick the last coin is the looseApproach
min 1 and max7 so total =8
now in first case he will leave in form of 8k
so he will leave 24 coins and will pick 6 coins in first turn
2nd case = he will leave 8k+1 form
8k+1 =25
so he will leave 3025=5 coinsQuestion= Number of coins = 22, A starts min = 4 max = 8 ,the one who picks last loses. how much should A pick up and if no of matchsticks falls below 4, the game ends
Approach
N = 22 min 4 and max =8 so sum 12 and 22= 12K + 10
to win A has to ensure that at the end, 4/5/6/7 matchsticks are left
so he picks up 6/5/4 matchsticks..
Now understand why ?
A piked up 4 then left =6
B has to pick 4 matchstick after which left = 64 = 2
A wins. because below 4 not acceptable.
now if A picked 6 then left with 4 so B has to pick this 4 so 0 left not possible
now if A picked 7 then 3 left so he will loose the game so he have to pick in range of
3 < pick coin < 7 so 4,5,6 .Question  998 balls, min balls to be picked4, max balls to be picked7. Two person A and B playing the game and last one picking the ball wins the game.How many balls should a person starting the game must pick in order to win .
Approach
11k + 8, now the person who wants to win should leave either 1 or 2 or 3 balls after picking the balls
so that the next person is not able to pick any ball as min balls to be picked is 4.
So that person can start with either 7 or 6 or 5 balls and create a gap of 11.
In that case other person will be left with 1 or 2 or 3 balls respectively and will not be able to pick any ball and hence lose the game. So 3 possibilities are there.
998=11k+8 (sum of minimum and maximum one can pick)
So, to win he should pick 5 or 6 or 7, as in these cases 3 or 2 or 1 will be left and 2nd person won't be able to pick anything