Provide a proof by mathematical induction for the following scenario: Instructio

Question

Provide a proof by mathematical induction for the following scenario:

Instructions: Start with a pile of objects and two players. In this game both platers will take turns taking 1 or 2 objects from the pile of objects. The goal of the game is to be  the one that takes the last objects.

Theorem to prove: if we start off with objects and player 1 were to always start (meaning go first), then Player 1 will always win if the objects on the table are not a multiple of 3, but Player 1 will always loose if the objects on the table are a multiple of 3.

Explanation / Answer

Let the number of objects in the pile be n.

First let us consider multiples of 3. Then n=3k and we would use induction on k, k=1,2,3,.....

For k=1, n=3. Then the first player would take either 1 or 2 objects, then the second player would take all the remaining objects and win the game.

Suppose the player 2 wins when k<m. And let us prove that player 2 wins for k=m.

Then n=3m, And suppose player 1 picks up 1 object, then player 2 picks up 2 objects , then we are left with 3(m-1) objects with player 1 to move , and by induction hypothesis , player 2 wins when the number of objects are a multiple of 3.

Now suppose n is not a multiple of 3, then player 1 will pick up 1 object if n=3p+1 type ,otherwise player 1 picks up 2 objects if n=3p+2 type. Now player 2 is the first to move with number of objects as multiple of 3. By the previous result, player 1 wins in this case.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.