CS1050: Understanding and Constructing Proofs Spring 2006 Lecture 09a: PROOF STRATEGIES Section 3.1 Jarek Rossignac Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 1 Lecture Objectives
Learn techniques for constructing proofs Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 2 How to cook 3 steaks? You have 3 steaks. Each one must be cooked for 1 mns on each side. The pan can hold only 2 steaks. Find the most time-effective strategy Prove that it works Prove that it is optimal
Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 3 What is forward reasoning? To prove an implication Start from the hypothesis Build a chain of implications that use the know axioms to lead to the conclusion Difficulty The path may not be obvious
Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 4 What is backward reasoning? Start with the conclusion. Build a chain of implications that use the know axioms backwards First the one that leads to the conclusion Then one that leads to this one Until you get to the hypothesis
Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 5 What is indirect reasoning? To prove an implication, Start the negation of the conclusion Build a chain of implications that use the know axioms to lead to the negation of the hypothesis Jarek Rossignac http://www.gvu.gatech.edu/~jarek
MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 6 How to win at Nim with 1 pile Pile of 15 stones. Each player removes 1, 2, or 3 stones from the pile. The person removing the last stone wins. Is there a winning strategy for player 1? Hint: Prove that if player 2 has to pick from a pile of 4, then
player 1 will win. Use backward reasoning to prove this for different (suitable) starting conditions. What should be the first move of player 1? Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 7 What are conjectures? You do not know whether a conjecture is true. Hence, you may try both proving it and looking for a counterexample.
Example: p(n)=n2+n+41, nN p(n) is prime (Euler 1772) N = {natural numbers, 0,1,2,3.} Prime: integer >1 and only divisible by itself and 1 (only 2 factors) Positive integer = product of primes (increasing order: canonical) It works! p(0)=41, p(1)=34, p(2)=47. P(3)=53p(39)=1601 are all prime! Does it? (Proof of contrary by counterexample) p(40)=402+40+41= 402+240+1=(40+1)2 =1681 is not prime Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006
8 Why are open problems important? They inspire research and sometimes lead to new branches in mathematics. Example of Fermats last theorem: The equation xn+yn = zn with integers x, y, z, n has no solution for n>2. Note that for n=2, we have Pythagorean triplets (3,4,5) Fermat claimed to have a proof. None could be found for about 300 years. Andrew Wiles developed a complex proof in 1990. Goldbach conjecture: Every even integer larger than 3 is the sum of two primes. Checked up to 1014 No proof or counterexample found yet! Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC
MAGIC Georgia Tech, IIC, GVU, 2006 9 What is the halting problem An example of an unsolvable problem, Let H(P,I) be a program which takes as input any program P and the input data I for P and returns true if P(I) is guaranteed to stop and false otherwise. Alan Touring has proven in 1936 that no such H exists. Proof by contradiction: Assume H exists. Make a program K(P) which loops forever if H(P,P) and halts otherwise. Consider K(K). If H(K,K) then K(K) loops forever, but H(K,K) indicates that it halts (contradiction). If !H(K,K) then K(K) halts, but !H(K,K) indicates that it loops forever (contradiction).
Conclusion, H does not exist. Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 10 Assigned Reading 3.1 Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC
MAGIC Georgia Tech, IIC, GVU, 2006 11 Assigned Exercises for the quiz Page 223-224: 1, 2, 20. 2: n=1+2k then n2 mod 8=1 Hint: direct proof develop n2 Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006
12 Assigned Project Jarek Rossignac http://www.gvu.gatech.edu/~jarek MAGIC MAGIC Georgia Tech, IIC, GVU, 2006 13
