CSE 20 DISCRETE MATH
Dive into the world of knights and knaves with logic puzzles involving truth-telling and lying individuals. Explore scenarios where you need to determine the identities of mysterious characters based on their statements. Test your reasoning skills with these engaging riddles.
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
Clicker frequency: CA CSE 20 DISCRETE MATH Prof. Shachar Lovett http://cseweb.ucsd.edu/classes/wi15/cse20-a/
Todays topics Knights and knaves
Knights and Knaves Knights and Knaves scenarios are somewhat fanciful ways of formulating logic problems Knight: everything a knight says is true Knave: everything a knave says is false 2+2=4 2+2=3
You approach two people, you know the one on the left is a knave, but you don t know whether the one on the right is a knave or a knight. Left: Everything she says is true. Right: Everything I say is true. What is she (the one on the right)? A. Knight B. Knave C. Could be either/not enough information D. Cannot be either/situation is contradictory
You approach one person, but you dont know whether he is a knave or a knight. Mystery person: Everything I say is true. What is he? A. Knight B. Knave C. Could be either/not enough information D. Cannot be either/situation is contradictory
You approach one person, but you dont know whether she is a knave or a knight. Mystery person: Everything I say is false. What is she? A. Knight B. Knave C. Could be either/not enough information D. Cannot be either/situation is contradictory
You meet 3 people: A: At least one of us is a knave. B: At most two of us are knaves. [C doesn't say anything] This is a really tricky one, but take a moment to see if you can determine which of the following is a possible solution: A. A: Knave, B: Knave, C: Knave B. A: Knight, B: Knight, C: Knight C. A: Knight, B: Knight, C: Knave (Suggestion: eliminate wrong choices rather than trying to solve the puzzle directly. In your groups: please discuss logic for eliminating choices.)
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.
You meet 3 people: A: At least one of us is a knave. B: At most two of us are knaves. [C doesn't say anything] A: Knight, B: Knight, C: Knave Zeroing in on just one of the three parts of the solution, we will prove by contradiction that A is a knight.
A: At least one of us is a knave. B: At most two of us are knaves. [C doesn't say anything] Thm. A is a knight. Proof (by contradiction): Assume not, that is, assume A is a knave. Try it yourself first!
A: At least one of us is a knave. B: At most two of us are knaves. [C doesn't say anything] Thm. A is a knight. Proof (by contradiction): Assume not, that is, assume A is a knave. Then what A says is false. Then it is false that at least one is a knave, meaning zero are knaves. So A is not a knave, but we assumed A was a knave, a contradiction. So the assumption is false and the theorem is true. QED.
You meet 3 people: A: At least one of us is a knave. B: At most two of us are knaves. [C doesn't say anything] A: Knight, B: Knight, C: Knave Zeroing in on the second of the three parts of the solution, we will prove by contradiction that B is a knight.
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!
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.
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.
You meet 3 people: A: At least one of us is a knave. B: At most two of us are knaves. [C doesn't say anything] A: Knight, B: Knight, C: Knave Zeroing in on the second of the three parts of the solution, we will prove by contradiction that C is a Knave.
A: At least one of us is a knave. B: At most two of us are knaves. [C doesn't say anything] Thm. C is a knave. Proof (by contradiction): Assume not, that is, assume C is a knight. Try it yourself first!
A: At least one of us is a knave. B: At most two of us are knaves. [C doesn't say anything] Thm. C is a knave. Proof (by contradiction): Assume not, that is, assume C is a knight. We already proved that A and B must be knights, hence telling the truth. So, if all three are knights, then A is lying, which is a contradiction. So, C must be a knave.
Next class Infinite set sizes, and diagonalization
