Suppose we fill a bag with R red and W white poker chips. We play the...

Transcribed Image Text:

Suppose we fill a bag with R red and W white poker chips. We play the following game: At each step, we remove two chips. Then, • if both the chips are red, we put one of the red chips back in the bag. • if one chip is red and the other is white, then we put the white chip back in the bag. • if both chips are white, then we put a red chip in the bag. We repeat this until there are not two chips left in the bag to remove. (Assume we have any needed extra red chips around if we, say, get two white chips on our first step.) a. (2 pts) Prove that we must eventually get to a situation where there is exactly one chip left in the bag. (Note: this does not involve induction.) We wish to determine the color of the last remaining chip. To do this, we'll establish an invariant. b. (6 pts) Use induction to establish the following invariant: Invariant: The parity of the number of white chips in the bag does not change. Make sure to state explicitly what P(n) is and what the induction hypothesis is. Hint: let R, and W; be the number of red and white chips, respectively, in the bag after i steps have been performed. c. (2 pts) Suppose the initial number of red chips in the bag (R) is a positive even integer and the initial number of white chips in the bag (W) is positive odd integer. Use the invariant from part b to prove that the last remaining chip is white. Suppose we fill a bag with R red and W white poker chips. We play the following game: At each step, we remove two chips. Then, • if both the chips are red, we put one of the red chips back in the bag. • if one chip is red and the other is white, then we put the white chip back in the bag. • if both chips are white, then we put a red chip in the bag. We repeat this until there are not two chips left in the bag to remove. (Assume we have any needed extra red chips around if we, say, get two white chips on our first step.) a. (2 pts) Prove that we must eventually get to a situation where there is exactly one chip left in the bag. (Note: this does not involve induction.) We wish to determine the color of the last remaining chip. To do this, we'll establish an invariant. b. (6 pts) Use induction to establish the following invariant: Invariant: The parity of the number of white chips in the bag does not change. Make sure to state explicitly what P(n) is and what the induction hypothesis is. Hint: let R, and W; be the number of red and white chips, respectively, in the bag after i steps have been performed. c. (2 pts) Suppose the initial number of red chips in the bag (R) is a positive even integer and the initial number of white chips in the bag (W) is positive odd integer. Use the invariant from part b to prove that the last remaining chip is white.

Answer rating: 100% (QA)

a At each step 2 chips are removed and 1 is added back Let there are n number of chips After a step ... View the full answer