Tackling Coin Picking Problems


  • Director at ElitesGrid | CAT 2016 - QA : 99.94, LR-DI - 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 loser

    Approach= 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 = 6

    Method2 (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 winner

    EXAMPLE- 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 = 100

    Shortcut = (n-1)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 = 5

    or Method-2 (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 100

    EXAMPLE- 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 loose

    Approach

    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 30-25=5 coins

    Question= 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 = 6-4 = 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 picked-4, max balls to be picked-7. 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


Log in to reply
 

Looks like your connection to MBAtious was lost, please wait while we try to reconnect.