A5P2: Using the Strong Principle of Mathematical Induction, prove for all intege

Question

A5P2: Using the Strong Principle of Mathematical Induction, prove for all integers n3 that if a team of n players plays the game Three May Share a Multiple of Three, then it is possible for the team to eventually win the game. (This is the game that we played and discussed at length in class. Copies of the rules are posted in the Handouts folder of the Content page on D2L..) Hint: It may be useful to break up the proof of your induction step of your argument into separate cases, depending on whether Player 3 starts the game with a number of cards that is (i) a multiple of 3 (i.e., of the form 3j for some positive integer j), (ii one more than a multiple of 3 (i.e., of the form 3j +1 for some positive integer j), or i two more than a multiple of 3 (i.e., of the form 3j +2 for some positive integer j).

Explanation / Answer

Case n =3.
In this case it is trivial that the team wins, for each player starts with 1 card each.

Case n = 4.
Player 1 starts with 1 card, 2 with 1 card and 3 with 2 cards. Now if players 2,3 and 4 can come together they will have 3 cards in total. 3 is evenly divisible by 3, so they may divide the cards among themselves as they wish. So player 3 may give on card to 4 and win.

Case n>4

Induction Hypothesis: Suppose the team of size k can win the game all k less than equal to n-1.

Now consider a team with size n.

Now by eucledian algorithm n = 3j, or 3j+1 or 3j+2 for some positive integer j.

Case 1: n = 3j+2.
In this case player 3 starts with 3j many cards.

Now players 3,4 and 5 may come togther and have a total of 3j cards among them. Since 3j is divisble by 3, they may divide the cards in a such a way that 3 has 3j-1 cards, 4 has 1 card and 5 has 0 cards.

Now remove player 4 from the game. Then we are back to the situation of n-1 players with n-1 cards such that player 1 has 1 card, player 2 has 1 card and player 3 has 3j-1 = n-3 = (n-1)-2 cards. By induction hypothesis there is a way by which team can win this game.

Since player 4 already has a card, thus if follows that when n = 3j+2 there is a way by which the team can win.

Case 2: n = 3j+1, where j is a positive integer

Now we start as follows
Player one: 1 card
Player 2: 1 card
Player 3: 3j-1 card
Players 4 upto n has no cards.

Now players 2, 3 and 4 can come togther and have a total of 3j-1+1 = 3j cards. So they may divide the cards as they wish. Do it in such a way that the cards are distributed as follows;
Player one: 1 card
Player 2: 1 card
Player 3: 3j-2 = (n-1)-2 card
Players 4: 1 card
Players 5 upto n has no cards.

Remove Player 4.
Then we obtain a game with n-1 players as we had above. By induction hypothesis there is a strategy to distribute 1 card each to each player.

After that bring player 4 back into the play. So now we have distributed n cards in such a way that each player has 1 card. So it follows that the team of size n can win the game if n = 3j+1 for some positive j.

Case n = 3j
Note that since n>4, we at least have 6 players in this case.


In this case we start as follows
Player 1: 1 card
Player 2: 1 card
Player 3: 3j-2 card
Players 4 upto n : no cards.

This time Players 1,2 and 3 shall come together and divide cards as follows
Player 1: 0
Player 2: 3
Player 3: 3j-3
Others : 0
Now Players 2,4 and 5 shall come togther and divide cards so that we have following situation
Player 1: 0
Player 2: 1
Player 3: 3j-3
Player 4:1
Player 5:1
Others: no cards

Now players 1,3 and player different from 2,4 and 5 can come together and divide the 3j-3 cards,so as to have the following situation (here player 3 shall give one card to player 1 and nothing to the other player)

Player 1: 1
Player 2: 1
Player 3: 3j-4
Player 4:1
Player5 : 1
Others: no card.

Now remove players 4 and 5 from the game. Then we are in a situation of n-2 players such that
Player 1 has 1 card
Player 2 has 1 card
Player 3 have 3j-4 = n-4 = (n-2)-2 cards
and other players have no cards.

By induction hypothesis there is a way to win the game when the size of team is less than n, so it follows that there is a way to distribute cards in a such a way that each player has 1 card.

Once that is done, bring players 4 and 5 back into the mix.

Thus we have that the game can be won if the team size is n = 3j for some positive integer j.

Combining all cases we have that a team of size n can win the game eventually if all teams of size less than n can win the game.

Since we have shown that teams of size 3 and 4 can win the game, it follows by induction that for all n, a team of size n can win the game.

PS: Please include all the necessary information from next time. I had to obtain the game rules from another question on chegg, by performing a search. Actually I stumbled upon it, while trying to figure out the rule using a search engine. Otherwise I would have had to skip the question. :)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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