Home

Passing alternating numbers of coins around

1,521.3K Views
Answered

A game is played as follows. N people are sitting around a table, each with one penny.  One person begins the game, takes one of his pennies (at this time, he happens to have exactly one penny) and passes it to the person to his left.  That second person then takes two pennies and passes them to the next person on the left.  The third person passes one penny, the fourth passes two, and so on, alternating passing one and two pennies to the next person. Whenever a person runs out of pennies, he is out of the game and has to leave the table. The game then continues with the remaining people.

A game is terminating if and only if it ends with just one person sitting at the table (holding all N pennies).  Show that there exists an infinite set of numbers for which the game is terminating.

Share
ronret45 Expert Asked on 1st August 2015 in Microsoft Interview Puzzles.
Add Comment
Cancel

    • 1 Answer(s)
    Best answer

    Either n= 2^x   +1,2^x   +2

    Proof
    suppose n=2k+1
    now after one round only k will be left with last one having 3 coins.if k is odd
    then after 2 rounds you will arive at same situation .to end it k must be even.if not understood  if kth(supposing k is odd) will have 2 extra coins at end of round which  it have to pass but for now we stopped the round
    then every one will go one through -1 +1…. and then  +1-1 nullifying effect no of coins wont chance because every one would have atleast 2 coins.

    suppose n is 2k then after 1 round k-1 will be left with last one having 3 coins no k-1 will be 2^x   + 1  (read all what i have written before).n is 2^(x+1 )      +2

    Cancel
    Yodha Expert Answered on 7th February 2016.
    Add Comment
    Cancel

    • Your Answer

    By posting your answer, you agree to the privacy policy and terms of service.

  • More puzzles to try-

  • Accenture Interview PuzzlesAdobe Interview PuzzlesAge RiddleAkbar Birbal PuzzlesAlgorithm PuzzlesAlphabet riddleAmazon Interview PuzzlesAnalytical MathematicsAptitude PuzzleBank PuzzlesBetting PuzzlesBrain TeasersCalendar PuzzlesCards PuzzlesChess Board PuzzleChess PuzzlesChristmas Puzzlecipher PuzzleCivil Services PuzzleClock time puzzleCognizant Interview PuzzlesCoins PuzzleComputational PuzzleconundrumCoronavirus PuzzleCoupondunia Interview PuzzleCritical Thinking Puzzledata analyticsData Structure Interview QuestionsDecode PuzzleDetective PuzzlesDice PuzzleDictionary Riddlesdifficult riddleEasy Math puzzlesEasy puzzlesEinstein puzzleEnglish RiddleFamily Tree Puzzlefamous puzzleFill in the blanks riddlesFinding Killer RiddlesFlipkart interview puzzlesFunny RiddlesGeneral KnowledgeGeographical PuzzleGoogle Code Jam 2014Google Interview PuzzlesGRE PuzzleHard Puzzle