6.042/18.] Mathematics for Computer Science February 15, 2005 Srini devadas and Eric Lehman Problem set 3 Solutions Due: Tuesday, February 22 at 9 PM Problem 1. An urn contains 75 white balls and 150 black balls. while there are at least 2 balls remaining in the urn, you repeat the following operation. You remove 2 balls elected arbitrarily and then: If at least one of the two balls is black, then you discard one black ball and put the other ball back in the urn If both of the balls are white then you discard them both and put a new black ball into the urn Prove that the urn never reaches the state where it is empty except for one black ball Solution. We use induction. Let P(n)be the proposition that the urn always contains an odd number of white balls Base case. Initially, the urn contains 75 white balls, which is an odd number, so P(O)is true Inductive step. Suppose that the urn contains an odd number of white balls after n steps If there are fewer than 2 balls remaining, then the process ends. Otherwise, there are then two cases 1. You draw at least one black ball. Then the number of black balls decreases by one and the number of white balls is unchanged. Therefore, the number of white balls remains odd 2. You draw two white balls. Then the number of black balls increases by one, and the number of white balls decreases by two. Again, the number of white balls remains Thus, the urn still contains an odd number of white balls after n+ l steps. By induction, the urn always contains an odd number of white balls. Therefore, the urn can never hold just one black ball and zero white balls, since zero is even. Problem 2. A puzzle toy contains the numbers l,..., 35 written on small circular disks. The disks are arranged on an oval track with no gaps so that the whole sequence of disks can slide clockwise or counterclockwise around the track6.042/18.062J Mathematics for Computer Science February 15, 2005 Srini Devadas and Eric Lehman Problem Set 3 Solutions Due: Tuesday, February 22 at 9 PM Problem 1. An urn contains 75 white balls and 150 black balls. While there are at least 2 balls remaining in the urn, you repeat the following operation. You remove 2 balls selected arbitrarily and then: • If at least one of the two balls is black, then you discard one black ball and put the other ball back in the urn. • If both of the balls are white, then you discard them both and put a new black ball into the urn. Prove that the urn never reaches the state where it is empty except for one black ball. Solution. We use induction. Let P(n) be the proposition that the urn always contains an odd number of white balls. Base case. Initially, the urn contains 75 white balls, which is an odd number, so P(0) is true. Inductive step. Suppose that the urn contains an odd number of white balls after n steps. If there are fewer than 2 balls remaining, then the process ends. Otherwise, there are then two cases: 1. You draw at least one black ball. Then the number of black balls decreases by one and the number of white balls is unchanged. Therefore, the number of white balls remains odd. 2. You draw two white balls. Then the number of black balls increases by one, and the number of white balls decreases by two. Again, the number of white balls remains odd. Thus, the urn still contains an odd number of white balls after n + 1 steps. By induction, the urn always contains an odd number of white balls. Therefore, the urn can never hold just one black ball and zero white balls, since zero is even. Problem 2. A puzzle toy contains the numbers 1, . . . , 35 written on small circular disks. The disks are arranged on an oval track with no gaps so that the whole sequence of disks can slide clockwise or counterclockwise around the track