How to solve problems

Some notes from the book How to Think Like a Mathematician by Kevin Houston. I found this chapter in the book interesting because I was able to relate to the  process when solving competitive programming problems.

Definitions

• Exercise - something that can be solved by a routine method
• Problem - something that will require more thought; will require the application of routine methods learned in exercises

"The best way to learn how to solve problems is to solve problems."

Sample Problems

1. How many zeroes are at the end of 100! (100 factorial)
2. Suppose that X and Y are two infinite sets. Find a formula that relates |X|, |Y|, | X intersection Y| and |X union Y|.
3. Show that the equation x^2 + y^2 = z^n has positive integer solutions for every n = 1,2 ,3, ...

Polya's four-step plan

Understanding the problem

1. Understand all the words and symbols in the problem - Know the meaning of the symbols as well as the important definitions and theorems
2. Guess - use your intuition - Make an educated guess
3. What do you know about the hypothesis and conclusion? - Write down what you know about the hypothesis and conclusion
4. Work backwards and forwards - You can start with the conclusion and think what it would imply.
5. Work with initial and special cases - Some problems have an index (n in P3). Solve for the initial cases to get a 'feel'.
6. Work with a concrete case - For abstract problems, look at a concrete case. Create instantiations of the variables. (P2)
7. Draw a picture - Venn diagrams (P2)
8. Think about a similar problem - Recall problems you've solved before that may be related to the problem you are solving.
9. Find an equivalent problem - Reformulate a problem, say to show that two functions are equal, they can be represented as a new function with difference of zero.
10. Solve an easier problem - In P1, solve 10! first to get a feel.
11. Rewrite in symbols or word -

Devising a plan

1. Break the problem into pieces -
2. Find the right level - there are many ways to approach a problem so select the right one
3. Give things names - "Let X be ..."
4. Systematically choose a method - A proving problem can be solved solve using different approaches.

Executing a plan

1. Check each step - don't use intuition

Looking back

1. Check the answer - Test.
2. Find another solution
3. Reflect - Think about what solved the problem.