# NSF CARGO: Multi-scale Topological Analysis of Deforming ...

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

## Recently Viewed Presentations

• Today we will be adding on to our knowledge and respect of beliefs! MONOTHEISM. Judaism, Christianity, and Islam are major faiths that are examples of . monotheism, or belief in one supreme god. I. JUDAISM. First practiced by a small...
• Sentence 1 Sentence 2 Sentence 3 What is something you learned about deleting to revise? APK (Day 2) We have learned that when we delete to revise we take out words or sentences that are not related to the main...
• When John heard in prison what the Messiah was doing, he sent word by his disciples and said to them, 'Are you the one who is to come, or are we to wait for another?' Jesus answered them, 'Go and...
• Two centuries later, Rugby Football has evolved into one of the world's most popular sports. It's a game of all shapes and sizes, each position requires different skills and physical attributes. Rugby still maintains a unique ethos, not only is...
• Key Terms Normal Structure and Function acetabulum The bony socket in the hip bone that holds the head of the femur (from the Latin word for vinegar because it resembles the base of a vinegar cruet) articulation A joint (adjective:...
• "As news of data security breaches at high-profile companies keeps coming, so too does the need for security planning and management skills. IT security is one of the top 10 skills that will become "newly important" to companies in the...
• Students across Kentucky are required to complete an Individual Learning Plan (ILP). The Career Cruising ILP Tool is designed to help students bring together their academic achievements, extracurricular experiences, and career and education exploration activities.
• Operations Philip Edwards Head of Science Operations 28 October 2008 Operations: Themes, Streams and Projects Structure End of an era… Science Operations Telescope Operations and Science Services TAC met; schedules for 2008OCTS out; ATS Project Submitted Joint TOSS/SCA/CI discussions on...