4. The Homework\'s Raisin Game. There is a competitive game for two players that

Question

4. The Homework's Raisin Game. There is a competitive game for two players that works as follows. The game begins with a handful of raisins split into two separate (and not necessarily the tabie. The players alternate taking complete turns until one of them le to take a complete turn; that player loses the game. A complete turn consists of two steps: First, the player eats one of the piles on the table. Second, the player divides the g the equal!) piles on remaining pile into two new pies (of arbitrary sizes, but non-empty), thus compietin urn (a) Find some classmates to play with. Play the game a few times with your classmates As we hinted in class, start small, and keep track of who wins which games, Player 1 or Player 2 (b) You will find that the winner depends very much on what the initial configuration of raisins looks like (that is, how many are in each pile). Make a conjecture: For what "ideal" configurations of raisins does Player 1 have a winning strategy? Again, muster the troops for this part talk with your classmates, come to office hours. (c) Try to prove that your "ideal configuration" indeed describes all winning positions for Player 1 (and also that all other configurations represent losing positions. That is, try to give a convincing argument that your conjecture is correct. (You are free to assume that each piayer will play according to an optimal winning strategy.)

Explanation / Answer

We will analyze the combinations of the number of raisins in the two piles one by one.

Consider the following situation.

                                    {1,1}                           

Clearly the player whose turn it is loses as he cannot divide 1 raisin.

Now consider the following situation.

                                    {2,x}

x can be any number. The player whose turn it is will win as he will eat x raisins and divide 2 into (1,1).

Now consider the following:

                                  {3,1}

The player whose turn it is will lose as he is forced to eat 1 and divide 3 into (2,1).

Now consider:

                              {3,3}

                                  

The player whose turn it is will lose as he will eat 3 and can divide 3 into only (2,1) (the situation (2,x)).

Again consider:

                                  {4,x}

Now the player whose turn it is will win as he will eat x raisins and divide 4 raisins into (3, 1).

Further consider:

                                    {1,5}

Now the player whose turn it is will lose as has to eat 1 and divide 5 into (2,3) or (4,1).

Finally consider:

                                      {6,x}

The player whose turn it is will win as he will eat x and divide 6 into (1,5) or (3,3).

From these results, the following pattern emerges in terms of the umber of raisins remaining for the player whose turn it is to play.

(Odd,Odd): Lose

(Odd,Even), (Even,Odd), (Even, Even): Win

So clearly, the initial combination matters. The player who starts can force a win if he has any of (Odd,Even), (Even,Odd) or (Even,Even) combinations initially. On the other hand, if the initial combination is (Odd,Odd), his opponent can force a win.

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

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