闪电代写 -代写CS作业_CS代写_Finance代写_Economic代写_Statistics代写_代码代做_IT代写_加急帮助

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CSE 21 Fall 2021

Homework 1 practice problem solutions

1. Suppose you have a red cup and a green cup. At the start, the red cup contains some number r red jellybeans (and nothing else) and the green cup contains some number g green jellybeans (and nothing else). Then, in each step, you take one jellybean from each cup, mix them up, and put one jellybean back into each cup. Prove that, after any number of steps, the number of green jellybeans in the red cup is equal to the number of red jellybeans in the green cup.

Solution: The claim is that after any number of steps, the number of green jellybeans in the red cup is equal to the number of red jellybeans in the green cup. Let’s state the claim in a slightly diﬀerent way so that we can use mathematical induction to prove it:

Claim: for any n > 0, after n steps, the number of green jellybeans in the red cup is equal to the number of red jellybeans in the green cup.

Base Case: After 0 steps, there are 0 green jellybeans in the red cup and 0 red jellybeans in the green cup so the claim is true for n = 0.

Induction Step: Suppose for some k > 0 that after k steps, the number of green jellybeans in the red cup is x and the number of red jellybeans in the green cup is also x. Then after one more step, you would take one jellybean from each cup, mix them up, and put one jellybean back into each cup.

Case 1: you picked a red jellybean from the red cup and a red jellybean from the green cup. Then mixing has no eﬀect and you put a red jellybean back into each cup essentially having no eﬀect and so there are still x red jellybeans in the green cup and x green jellybeans in the red cup.

Case 2: you picked a red jellybean from the red cup and a green jellybean from the green cup. Then mixing them up could result in two diﬀerent possibilities. You could put the jellybeans back into the cups that they came from in which case there is no eﬀect and there are still x red jellybeans in the green cup and x green jellybeans in the red cup. Or, you could have mixed them up and put the green jellybean in the red cup and the red jellybean in the green cup. In this case, there are now x + 1 red jellybeans in the green cup and x +1 green jellybeans in the red cup so the claim is still true.

Case 3: you picked a green jellybean from the red cup and a green jellybean from the green cup. Similar to case 1, there would be no eﬀect.

Case 4: you picked a green jellybean from the red cup and a red jellybean from the green cup. Then mixing them up could result in two diﬀerent possibilities. You could put the jellybeans back into the cups that they came from in which case there is no eﬀect and there are still x red jellybeans in the green cup and x green jellybeans in the red cup. Or, you could have mixed them up and put the red jellybean in the red cup and the green jellybean in the green cup. In this case, there are now x - 1 red jellybeans in the green cup and x - 1 green jellybeans in the red cup so the claim is still true.

Conclusion: It follows by mathematical induction that the claim is true for any n > 0 and so it is true after any number of steps.

2. An amoeba reproduces by splitting itself into two amoebas. This means that the original amoeba dies and its two oﬀspring live on. Prove that if you start oﬀ with one amoeba then after any amount of time, the number of living amoebas is equal to one plus the number of amoebas who have died.

Solution:

proof :

Every time an amoeba dies, the number of dead amoebas increases by 1 and the number of living amoebas essentially increases by 1 (in the sense that one of the oﬀspring replaces the parent amoeba and the other oﬀspring is the extra 1.)

You start out with 1 living amoeba and 0 dead amoebas so initially, the claim is true. Then after n splits, the number of living amoebas increases by n ( to a total of n + 1) and the number of dead amoebas increases by n (to a total of n) therefore after any number of splittings, the number of living amoebas is equal to one plus the number of amoebas who have died.

3. Suppose you are in a dark room with 100 quarters spread out on the ﬂoor. Before you go in, you know that 10 of the quarters are “heads” up and 90 are “tails” up. Your job is to enter the dark room and separate the quarters into two subsets such that each subset has the same number of “heads up” coins. (you cannot feel the texture of the coins enough to distinguish them and you cannot see.)Explain your strategy, and prove its correctness.

Solution:

There are two tricks to this problem that may not have been obvious at ﬁrst glance. First of all, the piles that you make do not need to have the same number of coins. Second of all, you can ﬂip a coin over to change it from heads to tails or from tails to heads.

Strategy: Separate out 10 coins from the 100, this will be one of your subsets. Then, ﬂip over all 10 coins from that subset.

There should be the same number of heads in your set of 10 as there are in the remaining 90.

proof:

Suppose that you separate out 10 from the 100 and in those 10 coins, there are x heads and 10 - x tails. Then in the remaining subset of 90, there are 10 - x heads. If you ﬂip over all of the coins in your subset of 10, there will be x tails and 10 - x heads. So the number of heads in your subset of 10 is equal to the number of heads in the remaining 90.

4. Suppose you have a chocolate bar that is an n × m grid of chunks. (See the picture below). You wish to break apart the chocolate bar into its individual chunks. A single break consists of you dividing a single piece of the chocolate bar horizontally or vertically into two new pieces. What strategy will split the bar with the fewest number of breaks? Prove your answer.

Solution:

It turns out that no matter what order you break the chocolate, the number of breaks to get it to nm individual chunks will always be nm - 1!!!

proof :

Every time you break one piece into two pieces, you have increased the number of pieces by 1. You start with one piece and you end with nm pieces. If each break increases the number of pieces by 1 then you need nm - 1 breaks to get from 1 to nm.