《Mathematics for Computer》Lecture 2 Notes for recitation

6.042/18.] Mathematics for Computer Science February 4, 2005 Srini devadas and Eric Lehman Notes for recitation 2 1 Case analysis The proof of a statement can sometimes be broken down into can be tackled individually 1.1 The method In order to prove a proposition P using case analysis Write, We use case analysis Identify a sequence of conditions, at least one of which must hold. (If this is not obvious, you must prove it. · For each condition State the condition Prove P assuming that the condition holds Often case-analysis arguments extend to several levels. The most difficult challenge in a case-analysis argument is try to decide how to break up the problem. The most common error is failing to construct a complete set of cases 1.2 Example Theorem 1. There exist irrational numbers p and q such that p raised to the power q is rational This is an ingenious proof, not the sort of thing one would think up in a few minute Proof. We use case analysis. Let v There are two cases Case 1: v is rational. Let p=g=v2. Then p?=v is rational, so the claim holds

6.042/18.062J Mathematics for Computer Science February 4, 2005 Srini Devadas and Eric Lehman Notes for Recitation 2 1 Case Analysis The proof of a statement can sometimes be broken down into several cases, which then can be tackled individually. 1.1 The Method In order to prove a proposition P using case analysis: • Write, “We use case analysis.” • Identify a sequence of conditions, at least one of which must hold. (If this is not obvious, you must prove it.) • For each condition: – State the condition. – Prove P assuming that the condition holds. Often case­analysis arguments extend to several levels. The most difficult challenge in a case­analysis argument is try to decide how to break up the problem. The most common error is failing to construct a complete set of cases. 1.2 Example Theorem 1. There exist irrational numbers p and q such that p raised to the power q is rational. This is an ingenious proof, not the sort of thing one would think up in a few minutes. Proof. We use case analysis. Let v = √2 √2 . There are two cases: • Case 1: v is rational. Let p = q = √2. Then pq = v is rational, so the claim holds

Recitation 2 ·Case2: v is irrational.Letp= v and q=√2.Then Since 2 is rational, the claim holds

� Recitation 2 2 • Case 2: v is irrational. Let p = v and q = √2. Then: 2 pq = v √2 = √ 2 √2 �√2 = √ 2 = 2 Since 2 is rational, the claim holds

Recitation 2 Team Problem: An indirect Proof Here is the format of an indirect proof of a proposition P 1. We use proof by contradiction 2. Suppose P is false 3. Show this implies some sort of contradiction 4. " This is a contradiction Therefore, p is true Give an indirect proof of the following theorem. Theorem 2. log 8 is irrational Solution. We use proof by contradiction. Suppose that log, 8 is rational. Then there exist integers a and b such that ogsa This implies that (Raising the first equation to the b-th power gives the second. Now the left side of the last equation is even and the right side is odd. This is a contradiction. Therefore, log s 8 is irrational

Recitation 2 3 Team Problem: An Indirect Proof Here is the format of an indirect proof of a proposition P. 1. “We use proof by contradiction.” 2. “Suppose P is false.” 3. Show this implies some sort of contradiction. 4. “This is a contradiction. Therefore, P is true.” Give an indirect proof of the following theorem. Theorem 2. log5 8 is irrational. Solution. We use proof by contradiction. Suppose that log5 8 is rational. Then there exist integers a and b such that: a log5 8 = b This implies that: 8 = 5a/b 8b = 5a (Raising the first equation to the b­th power gives the second.) Now the left side of the last equation is even and the right side is odd. This is a contradiction. Therefore, log5 8 is irrational

Recitation 2 Team Problem: A Case analysis Four castaways must escape from an island to the mainland on a makeshift raft. Their weights are 5, 10, 20, and 25. The raft can hold at most two people. The number of minutes required to paddle the raft between the island and the mainland is equal to the weight of e heavies t passenger aboard. For example, if 10 and 25 cross together, 25 minutes are used. If 10 then returns alone another 10 minutes are used Claim 3. It takes at least 65 minutes for all four castaways to escape Proof. At least three trips and two return trips are required. Since the lightest person has weight 5, a minimum of 2.5= 10 minutes are required for the two return trips. The three forward trips then require a total of 55 minutes: 10 minutes for 5 and 10, 20 minutes for 5 and 20, and 25 minutes for 5 and 25. Therefore, the total time for all four people to cross is at least 10+55=65 minutes as claimed (a)Where is the error in this argument? Solution. The"proof"considers only the possibility that person 5 shuttles everyone else to shore (b) Find a way to get everyone to shore in 60 minutes Solution ·5and10 cross ·5 returns ·20and25 cross ·10 returns ·5and10 cross

Recitation 2 4 Team Problem: A Case Analysis Four castaways must escape from an island to the mainland on a makeshift raft. Their weights are 5, 10, 20, and 25. The raft can hold at most two people. The number of minutes required to paddle the raft between the island and the mainland is equal to the weight of the heaviest passenger aboard. For example, if 10 and 25 cross together, 25 minutes are used. If 10 then returns alone, another 10 minutes are used. Claim 3. It takes at least 65 minutes for all four castaways to escape. Proof. At least three trips and two return trips are required. Since the lightest person has weight 5, a minimum of 2 5 = 10 · minutes are required for the two return trips. The three forward trips then require a total of 55 minutes: 10 minutes for 5 and 10, 20 minutes for 5 and 20, and 25 minutes for 5 and 25. Therefore, the total time for all four people to cross is at least 10 + 55 = 65 minutes as claimed. × (a) Where is the error in this argument? Solution. The “proof” considers only the possibility that person 5 shuttles everyone else to shore. (b) Find a way to get everyone to shore in 60 minutes. Solution. • 5 and 10 cross • 5 returns • 20 and 25 cross • 10 returns • 5 and 10 cross

Recitation 2 (c) Flesh-out the case-analysis proof of the following theorem: Theorem 4. The four castaways can not escape in 55 or fewer minutes. Specifically, explain why there is no way for the four castaways to escape in 55 or fewer minutes in each case Proof. We use case analysis. We first consider the total number of boat trips Case 1. There are an even number of trips Solution. Then the boat ends up on the island. Whoever brought it over last is Case 2. There are three or fewer trips Solution. Then at most three people can escape the island Case 3. There are seven or more trips Solution. At least one trip takes 25 minutes. This trip excludes either 20 or 10, so another trip takes at least 10 minutes. The remaining trips take at least 5 minutes each. So the total time is at least 25+10+5. 5=60 minutes Case 4. There exactly five trips. Now we consider trips involving 20 and 25 Case A Multiple trips involve either 20 or 25 Solution. Then there is at least one 25 minute trip and at least one 20 minute trip. The remaining trips require at least 5 minutes each for a total 25+20+3.5=60 minutes Case b. No trips involve either 20 or 25 Solution Then they are stuck on the island Case C. Exactly one trip involves both 20 and 25. We now consider trips involving person 10 Case i. An even number of trips involve 10 Solution. Then 10 ends up on the island Case ii. Exactly one trip involves 10 Solution. This implies that 5 is the only passenger on one trip off the island. Thus, there are at most five departures from the island. Some- one must be in the boat for both trips back to the island, so there are at least two returns. But that means that someone is left stuck on the Case iii. Three or more trips involve 10 Solution. Then the total time for all four castaways to escape is at least 25+3·10+5=60

Recitation 2 5 (c) Flesh­out the case­analysis proof of the following theorem: Theorem 4. The four castaways can not escape in 55 or fewer minutes. Specifically, explain why there is no way for the four castaways to escape in 55 or fewer minutes in each case. Proof. We use case analysis. We first consider the total number of boat trips. • Case 1. There are an even number of trips. Solution. Then the boat ends up on the island. Whoever brought it over last is stuck there. • Case 2. There are three or fewer trips. Solution. Then at most three people can escape the island. • Case 3. There are seven or more trips. Solution. At least one trip takes 25 minutes. This trip excludes either 20 or 10, so another trip takes at least 10 minutes. The remaining trips take at least 5 minutes each. So the total time is at least 25 + 10 + 5 · 5 = 60 minutes. • Case 4. There exactly five trips. Now we consider trips involving 20 and 25. – Case A. Multiple trips involve either 20 or 25. Solution. Then there is at least one 25 minute trip and at least one 20 minute trip. The remaining trips require at least 5 minutes each for a total of 25 + 20 + 3 · 5 = 60 minutes. – Case B. No trips involve either 20 or 25. Solution. Then they are stuck on the island. – Case C. Exactly one trip involves both 20 and 25. We now consider trips involving person 10. * Case i. An even number of trips involve 10. Solution. Then 10 ends up on the island. * Case ii. Exactly one trip involves 10. Solution. This implies that 5 is the only passenger on one trip off the island. Thus, there are at most five departures from the island. Some￾one must be in the boat for both trips back to the island, so there are at least two returns. But that means that someone is left stuck on the island. * Case iii. Three or more trips involve 10. Solution. Then the total time for all four castaways to escape is at least 25 + 3 · 10 + 5 = 60