Mathematics for Computer Science

5.4. State Machines 153 Problems for Section 5.2 Practice Problems Problem 5.17. Some fundamental principles for reasoning about ...

Chapter 5 Induction154 False Claim.Every Fibonacci number is even. False proof. 1. We use strong induction. The induction hypot ...

5.4. State Machines 155 Then by strong induction hypothesis, Even.n/and Even.n1/are true, that is, F.n/andF.n1/are both even. Bu ...

Chapter 5 Induction156 Class Problems Problem 5.21. The Fibonacci numbersF 0 ;F 1 ;F 2 ;:::are defined as follows: FnWWD 8 ˆ< ...

5.4. State Machines 157 Inductive step: Suppose thatn 2 and thatiis a pusp for every integeriwhere 2 i < nC 1. We must show ...

Chapter 5 Induction158 thenpjxifor some 1 in. Bogus proof.Proof by strong induction onn. The induction hypothesis,P.n/, is tha ...

5.4. State Machines 159 Problem 5.28. A class of any size of 18 or more can be assembled from student teams of sizes 4 and 7. Pr ...

Chapter 5 Induction160 Problem 5.31. Prove that every amount of postage of 12 cents or more can be formed using just 4-cent and ...

5.4. State Machines 161 (b)Use the Invariant Method to prove that the algorithm is partially correct—that is, ifsD 0 , thenaDxy. ...

Chapter 5 Induction162 memory, the ant may choose to move forward one square, or it may turn right or left. It eats a crumb when ...

5.4. State Machines 163 (b)Use the Invariant Principle to prove that you cannot make the entire first half of the deck black thr ...

Chapter 5 Induction164 TheXORof the numbers of stones in the piles is called theirNim sum. In this problem we will verify that i ...

5.4. State Machines 165 “the impossible”): 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 A state machine model of the puzzle has states co ...

Chapter 5 Induction166 (b)Verify that the parity of the start state and the target state are different. (c)Show that the parity ...

5.4. State Machines 167 (a)Give a mathematical model of the Authority’s system for letting cars on and off the bridge by specify ...

Chapter 5 Induction168 Problem 5.40. Start with 102 coins on a table, 98 showing heads and 4 showing tails. There are two ways t ...

5.4. State Machines 169         Outbreaks of infection spread rapidly step by step. A student is infected after a step i ...

Chapter 5 Induction170 Exam Problems Problem 5.42. There is a bucket containing more blue balls than red balls. As long as there ...

5.4. State Machines 171 TheRotate-Triplecould also rotate the consecutive numbers2;4;1into1;2;4 so that .2;4;1;5;3/!.1;2;4;5;3/: ...

...