Ilya, here are notes you took for yourself

Problem Solving

Ilya, to solve a problem use these methods:

  • solve examples
  • use direct reasoning
  • work specific to general
    • remove or impose restrictions on problem
  • guess and check
    • try as many versitile hypotheses as possible
    • notice a pattern
  • work backwards
    • if f(u) = v, find u = f^-1(v)
    • use contrapositive
    • work from ending to beginning
  • work opposite
    • if f(u) = v, find all x : f(x) != v
    • work by contradiction
  • interpretation manipulation 
    • find equivalent form
    • manipulate formulas
    • restate the problem in other words
    • solve dual form
  • use known results, models, theorems
  • bruteforce, exhaustion
  • exploit special features
  • is problem a special case?

 

If and only if: Sometimes you are asked to prove something of the form "A if and only if B" or "A is equivalent to B." The usual way to do this is to prove two things: first, prove that "A implies B," and then prove that "B implies A." Use any of the possible techniques to prove these two implications.

Uniqueness: You are often asked to prove that some object satisfying a given property is unique. The trick is to assume that there is another object satisfying the property, and then show that it actually equals the original one.

Existence: This sort of proof often goes hand in hand with uniqueness. You are given some specified property, and then asked to show that an object exists which has that property. There are often two ways to do this. One can offer up a constructive proof, in which the object is explicitly constructed. A nonconstructive proof is the exact opposite - it shows that the object exists, but it gives no indication as to what the object looks like.

Existence and Uniqueness: As stated before, existence and uniqueness go hand in hand. Sometimes you will be asked to prove that an object satisfying some property exists and is unique. This can be done in either order. Sometimes it is easy to prove that the object exists, and then to show that it is unique. However, the existence proof may seem daunting, and it is often helpful to prove uniqueness first. The uniqueness proof may give some hints as to what the object must look like