Peer Instruction in Discrete Mathematics: Knights and Knaves
Dive into the world of Knights and Knaves with peer instruction in discrete mathematics by Dr. Cynthia Bailey Lee and Dr. Shachar Lovett. Explore proof by contradiction, Fibonacci numbers, and more in an engaging learning experience.
Download Presentation

Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Creative Commons License CSE 20 Discrete Mathematics Dr. Cynthia Bailey Lee Dr. Shachar Lovett Peer Instruction in Discrete Mathematics by Cynthia Leeis licensed under a Creative Commons Attribution- NonCommercial-ShareAlike 4.0 International License. Based on a work at http://peerinstruction4cs.org. Permissions beyond the scope of this license may be available at http://peerinstruction4cs.org.
2 Today s Topics: 1. Finish up Knights and Knaves (Proof by Contradiction) 2. Fibonacci numbers (Proof by Induction)
3 1. Knights and Knaves
4 Proof by Contradiction Steps What are they? A. 1. Assume what you are proving, 2. plug in definitions, 3. do some work, 4. show the opposite of what you are proving (a contradiction). B. 1. Assume the opposite of what you are proving, 2. plug in definitions, 3. do some work, 4. show the opposite of your assumption (a contradiction). C. 1. Assume the opposite of what you are proving, 2. plug in definitions, 3. do some work, 4. show the opposite of some fact you already showed (a contradiction). D. Other/none/more than one.
5 A: At least one of us is a knave. B: At most two of us are knaves. [C doesn't say anything] Thm. B is a knight. Proof (by contradiction): Assume not, that is, assume B is a knave. Try it yourself first!
6 A: At least one of us is a knave. B: At most two of us are knaves. [C doesn't say anything] Thm. B is a knight. Proof (by contradiction): Assume not, that is, assume B is a knave. Then what B says is false, so it is false that at most two are knaves. So it must be that all three are knaves. Then A is a knave. So what A says is false, and so there are zero knaves. So B must be a knight, but we assumed B was a knave, a contradiction. So the assumption is false and the theorem is true. QED.
7 A: At least one of us is a knave. B: At most two of us are knaves. [C doesn't say anything] Thm. B is a knight. Proof (by contradiction): Assume not, that is, assume B is a knave. Then what B says is false, so it is false that at most two are knaves. So it must be that all three are knaves. Then A is a knave. So what A says is false, and so there are zero knaves. But all three are knaves and zero are knaves is a contradiction. So B must be a knight, but we assumed B was a knave, a contradiction. So the assumption is false and the theorem is true. QED. We didn t need this step because we had already reached a contradiction.
8 2. Fibonacci numbers Verifying a solution
9 Fibonacci numbers 1,1,2,3,5,8,13,21, Rule: F1=1, F2=1, Fn=Fn-2+Fn-1. Question: can we derive an expression for the n-th term? n n + 1 1 5 1 1 5 YES! = n F 2 2 5 5
10 Fibonacci numbers Rule: F1=1, F2=1, Fn=Fn-2+Fn-1. We will prove an upper bound: + 1 5 = n , n F r r 2 Proof by strong induction. Base case: A. n=1 B. n=2 C. n=1 and n=2 D. n=1 and n=2 and n=3 E. Other
11 Fibonacci numbers Rule: F1=1, F2=1, Fn=Fn-2+Fn-1. We will prove an upper bound: + 1 5 = n , n F r r 2 Proof by strong induction. Base case: n=1, n=2. Verify by direct calculation = = 2 1 F r 1 F r 1 2
12 Fibonacci numbers Rule: F1=1, F2=1, Fn=Fn-2+Fn-1. + 1 5 Theorem: = n , n F r r 2 Base cases: n=1,n=2 A. Fn=Fn-1+Fn-2 B. Fn Fn-1+Fn-2 C. Fn=rn D. Fn rn E. Other Inductive step: show
13 Fibonacci numbers = + n Inductive step: need to show , 1 5 , n F r r 2 What can we use? Definition of Fn: Inductive hypothesis: = + F F F 2 1 n n n 1 2 n n , F r F r 1 2 n n That is, we need to show that r + 2 1 n n n r r
14 Fibonacci numbers Finishing the inductive step. Need to show: + 2 1 n n n r r r 1 r + 2 r Simplifying, need to show: = 1 r + = + 2 Choice of actually satisfied (this is why we chose it!) 1 5 r r 2 QED
15 Fibonacci numbers - recap Recursive definition of a sequence Base case: verify for n=1, n-2 Inductive step: Formulated what needed to be shown as an algebraic inequality, using the definition of Fn and the inductive hypothesis Simplified algebraic inequality Proved the simplified version