The jelly beans game begins with n 2 jelly beans on the table that are divided i

Question

The jelly beans game begins with n 2 jelly beans on the table that are divided into two nonempty heaps (piles of one or more jelly beans). The player whose turn it is to play loses the game if there are only two jelly beans on the table. Otherwise, she chooses one of the heaps and eats the jelly beans in that heap, then takes the remaining heap and splits it into two nonempty heaps in any way she wants (i.e., if the remaining heap had size 4 it could be split into new heaps of sizes 1 and 3, or heaps of sizes 2 and 2). As long as there are at least three beans, it is always possible to select the heap to be eaten so that the other heap can be divided into two nonempty heaps. (A player isn’t allowed to eat a heap that would leave just one bean on the table for the other heap.)

1. Suppose it is your turn to play. In each of the following cases state whether you will lose or win.

2. Use strong induction to prove that, for every n 2, the player whose turn it is to play wins exactly when at least one heap is even. That is, you are to show that (i) the player wins if one heap is even and (ii) the player loses if both heaps are odd.

(a) State and verify the base case.

(b) Write your induction hypothesis and the statement that should be proven from it.

(c) Perform the inductive step.

Explanation / Answer

1)
1 1 - the player clearly looses.
1 2 - the player will eat the only bean from heap '1' and split '2' into '1' '1' , thus winning.
2 2 - player eats from one bean from either one of the heaps and split the other into 1 1 - wins.
1 3 - player is forced to eat the only bean from heap '1'. Now the player has only option - that is to split '3' into '2' and '1'. The other player will eat '1' and then split '2' into '1' '1' - player looses.
2 3 - player will eat from '3' and split 2 into '1' and '1' - wins.
3 4 - player will eat from '3' split 4 into 3 and 1. The opposite player is forced to eat '1' and split 3 into '1' and '2'. Player eats '1' and splits '2' into 1 1 - wins.

2) Let the P(n) be the statement that 'the player wins if heap sizes are m, 2n, where m is an arbitrary positive integer
a) Then the base case or P(1) is 'the player wins if the heap sizes are m and 2 where m is any positive integer.

Proof: The player can clearly eat from the heap 'm', leaving the heap of size 2 intact. Now the player shall split '2' into '1' '1' and emerge the winner.

b) Induction hypothesis : P(n) is true up to all k, where k is a positive integer. That is 'the player wins if the heap size are of the form m, 2n where m is an arbitrary fixed integer and 0<n<k+1'.
Given this hypothesis we need to prove that P(k+1) is true that is the player wins if heap size are m and 2(k+1).

c) Initially the heap sizes are m and 2(k+1). Now the player can eat from heap 'm', because 2(k+1)=>4. Following this the player shall split '2(k+1)' into 2(k) and '2'. We have already assumed that if the heap size is of the form m, 2k then the player wins. So the player clearly wins if heap size is of the form m, 2(k+1) given that the player wins if heap size is of the form m,2k. Now since we have already established that player wins if heap size is of the form m,2 by induction player wins for all positive 'k' if heap size is of the form m,2k.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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