Challenge Solved!
The first challenge problem has been solved!
Challenge 1. From Class 2: I wasn’t very satisfied with
my proof of the “Odd-Even Lemma” in class. I hope a student will come
up with a better proof. Come up with a proof that passes the
“skeptical reader” test and would convince someone with no prior
knowledge of odd and even numbers.
There are three winning solutions (that all take quite different approaches):
- John Fry’s solution using the well-ordering principle
- Paul Sander’s solution using a game proof (although most game-style proofs are not so entertaingly written as Pauls, using a game to prove something is a very common strategy, especially in security and cryptography proofs.)
- Avi Parikh’s solution using proof by contradiction
Congratulations to the challenge winners!
(Challenge 2 is still open, and no viable solutions have yet been submitted.)