Suppose we fill a bag with R red and W white poker chips. We play the...
Fantastic news! We've Found the answer you've been seeking!
Question:
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.
Expert Answer:
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
Related Book For
Statistics For Business Decision Making And Analysis
ISBN: 9780134497167
3rd Edition
Authors: Robert A. Stine, Dean Foster
Posted Date:
Students also viewed these mathematics questions
-
At a local casino, one can play the following game for $10. The player tosses a die three times and earns the following winnings $10 for the first die that shows a 6 $15 more for the second die that...
-
An urn contains one red chip and one white chip. One chip is drawn at random. If the chip selected is red, that chip together with two additional red chips are put back into the urn. If a white chip...
-
An urn contains one white chip and one black chip. A chip is drawn at random. If it is white, the game is over; if it is black, that chip and another black one are put into the urn. Then another chip...
-
Kamloops Company is a grocery wholesaler and is planning to expand its operations. The company has asked the bank for a loan to finance the expansion. Alphonzo, the companys manager, has prepared the...
-
A mica sheet 1.2 m thick is suspended in air. In reflected light, there are gaps in the visible spectrum at 421, 474, 542, and 633 nm. Find the index of refraction of the mica sheet.
-
Coupon Cpn Freq Day Cnt Maturity 1.700000 S/A 30/360 02/22/2019 Type Fixed Composite AA+ Iss Price 99.98300 Issuance & Trading Amt Issued/Outstanding MAKE WHOLE @12.500000 until 02/22/19/BULLET Iss...
-
Use the comparative balance sheet from Application Problem 17-1 to complete this problem. Instructions: 1. Based on CyberOptics comparative balance sheet prepared in Application Problem 17-1,...
-
Suppose the demand for labor is given by L = 50w + 450 and the supply is given by L = 100w Where L represents the number of people employed and w is the real wage rate per hour. a. What will be the...
-
Using the appropriate method, dispose of the over- or under-applied overhead. Explain what other methods can be used and why you used the method that you did.
-
Write a program that produces calendars as output. Your program should have a method that outputs a single months calendar like the one below, given parameters to specify how many days are in the...
-
Marco S.A. is a French company that produces and sells 2 products, A and B. It uses 2 raw materials, X and Y for its production. It is organized in 5 departments: Administration, Maintenance,...
-
A rectangular conducting metal loop is being pulled out of an area with a constant magnetic field. The loop has a length L and width W, a resistance R, and is moving with a constant velocity v to the...
-
Carlin Company has current assets of $100,000, total assets of $1,000,000, current liabilities of $50,000, total liabilities of $250,000 and total equity of $750,000. What is the current ratio...
-
Using the following sites and other resources you choose, research the case of Cameron Todd Willingham. Then answer the following questions, make sure to include detailed answers and cite where you...
-
Bloom Corporation had the following 2025 income statement. Sales revenue $200,000 Cost of goods sold 120,000 Gross profit 80,000 Operating expenses (includes depreciation of $21,000) 50,000 Net...
-
This morning, thehair dryer of one of the students in this class broke. The student,Jane, discussed the problem with her older brotherDick. Dick: Hi,Jane. What happened to your hair dryer? Jane: It...
-
A basketball player stands in the corner of the court at the three - point line, 7.33 m from the basket, with hoop 3.25 m above the floor. ( a ) If the player shoots the ball from a height of 1.9 m...
-
With your classmates, form small teams of skunkworks. Your task is to identify an innovation that you think would benefit your school, college, or university, and to outline an action plan for...
-
Match each definition on the left with its mathematical expression on the right. Value of the response in the previous time period (a) Y 10 , Y 11 , Y 12 , Y 13 , Y 14 (b) b 0 + b 1 t (c) b 0 + 1 Y...
-
Without doing all the calculations, which of these 2 2 tables has the largest value of chi-squared? The smallest? (Each table has n = 100.) (a) (c) (b) 25 50 25 30 20 20 25 25 30 50 2.
-
Match each term from an ANOVA regression on the left to its symbol on the right. These exercises use the abbreviations SS for sum of squares and MS for mean squares. Observed response (a) b 0 (b) 1...
-
What is the median voter model?
-
The U.S. federal income tax is an example of a a. progressive tax. b. proportional tax. c. regressive tax. d. value-added tax.
-
What is public choice theory?
Study smarter with the SolutionInn App