# Problem Solving

Ilya, to solve a problem use these methods:

• use direct reasoning
• work specific to general
• remove or impose restrictions on problem
• guess and check
• solve examples
• try as many versitile hypotheses as possible
• notice a pattern
• work backwards
• if f(u) = v, find u = f^-1(v)
• work from ending to beginning
• work opposite
• if f(u) = v, find all x : f(x) != v
use contrapositive
• interpretation manipulation
• solve equivalent problem
• 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?
• draw a picture
• solve an equation
• look for a formula
• do a simulation
• use coodinates
• use symmetry
• identify subgoals

## Examples

### Use Direct Reasoning

Direct reasoning is the simplest form of problem solving, you just apply your knowledge.

Problem: "You have 10 apples you ate 3. How many apples do you have now?"

The solution is 10-3=7 apples.

### Work Specific to General

You can remove some restrictions from the problem, solve relaxed problem and then attach initial restrictions.

Problem: "Find a formula rotating point (x,y) aroung point (a,b) by angle A"

Remove restriction for rotation around point (a,b) - find a forumla for rotation around origin (0,0), assume you have found the formula for rotation around (0,0), then to rotate point (x,y) around (a,b) simply transfer the point to the origin (0,0) rotate it, and then transfer it back: Rotate((x-a,y-b))+(a,b)

### Guess and Check

Guess and check method is relied on pattern recognition and hypotheses: solve examples, make assumptions and see notice a pattern.

Problem: "You have 2 numbers A and B, every next day you set number A=HarmonicMean(A,B)*ArithmeticMean(A,B)/B and B=HarmonicMean(A,B)*ArithmeticMean(A,B)/A. What are the numbers A and B after 100 days?"

This problem is easily solved by actually writing down these numbers and noticing that they remain the same. The solution is: after 100 days A will be equal to A and B will be equal to B

Problem 2: "N people walk into a bar, everyone makes a handshake pairwise, how many handshakes were made?"

Hypothesis: formula is a polynomial. Interpolating the polynomial you find: N*(N+1)/2 handshakes were made.

### Work Backwards

Working backwards proposes you to find an invert function or restoring initial state of problem from a final solution and then backtracking.

Problem: "You have n houses on the x-axis with random coordinates, you need to place m people in these houses such that the minimal distance between neighbouring people is maximial."

Solving this problem directly might be difficult, you are trying tell from m people the maximal distance - build an invert statement: tell how many people you can fit in these houses using fixed distance. if you can't fit m people decrease your distance, otherwise increase it.

Problem 2 (Polya's example): "How can you bring up from the river exactly 6 quarts of water when you have only two containers, a 4 quart pail and 9 quart pail, to measure with?"

Solve this problem by backtracking from the solution, you have 6 quarts in your 9 quart pail, you got this 6 quars either by poring 4 quart pail into 9 quart pail when it had 2 quarts of water OR you you poured 3 quarts from 9 quart pail, you could do it if 4 quart pail had 1 quart of water. Exploring first possibility yields no result, but exploring second yields the solution. Solution:

 action 4 quart pail 9 quart pail initial 0 0 fill 9 quart 0 9 pour into 4 quart 4 5 empty 4 quart 0 5 pour into 4 quart 4 1 empty 4 quart 0 1 pour into 4 quart 1 0 fill 9 quart 1 9 pour into 4 quart 4 6 empty 4 quart 0 6

### Work Opposite

Working opposite requires you to do opposite of what your are trying to do

Problem: "If number n equals to p*q prove that either p or q <= sqrt(n)."

You are given a statement A and B and required to prove A->B, well, do the opposite: prove not(B)->not(A). The contrapositive statement is: "if p and q > sqrt(n) prove that p*q does not equal n". Now apply direct reasoning: if p and q > sqrt(n), then p*q>sqrt(n)*sqrt(n), which is the same as p*q>n, therefore p*q!=n. Therefore we proved not(B)->not(A), which is the same as A->B.

Problem 2: "There are 5 people in the room, what is the probability that atleast 2 of them have the same birthday?".

The statement is: "atleast 2 of them have the same birthday" is opposite of "none of them have the same birthday", and from probability theory: p=1-not(p). Apply direct reasoning to find probability that none of them have the same birthday: First guy has a birhday at a day D1 there are 365 days to chose from, second guy has birthday at a day D2, there are 364 days to choose from (he cant have birthday on day D1), etc.. The formula is: 365*364*363*362/(365*365*365*365) =0.98364408753. Therefore probability that atleast 2 of them have the same birthday is: 1-0.98364408753=0.01635591246.

Interpretation Manipulation

Without a doubt this is the most powerful method of solving any problem. It relies on finding a new problem which is equivalent to the initial one, you can draw the solution of initial problem from the solution of the equivalent problem.

Problem: "An infinite amount of mathematicians walk into a bar, first one buys 1 litre of beer, the second one buys 1/3 of what first one has bought, the third one buys 1/3 of what the second one has bought and so on. How many litres of beer did they buy?"

Transfer the problem to the realm of numbers and then manipulate formulas: total_beer=1+1/3+1/(3*3)+1/(3*3*3)... but at the same time total_beer/3=1/3+1/(3*3)+1/(3*3*3)+1/(3*3*3*3)... therefore total_beer-total_beer/3=1, solving for total_beer gives total_beer=3/2.

Problem 2: "You are given n girls and m boys, girls want to marry boys, given a list of boys every girl likes maximize number of girls to be married".

Transfer this problem into the realm of graphs: make girls and boys vertecies and add edge from every girl to all boys she likes. The resulting graph will be bipartite and the problem has a known algorithm: kuhn algorihm for maximal bipartite matching.

Problem 3:

In this example solving direct problem is unpleasant, however it's convex, you know that for convex problems solution to the Lagrangian lower bound solution is the same:

This problem yields solution to the original and has a nice algorithm to solve it: Sequential Minimal Optimization algorithm.

Problem 4: "Prove that there is no general finite formula using radicals to solve quintic polynomial"

The solution of this example is long, you saved this problem to notes only as the most notable example of how a problem which had absolutely no approach is solved by introducing an equivalent form: "The quintic equation is solvable if and only if the chain of commutator subgroups for it's Galois group is finite". Now the problem lies in the group theory. Galois group of a general quintic equation is S5, but the chain of its commutator subgroup gets stuck at A5. The problem is solved by solving an entirely different problem, one would even not notice and connection between the two.

Uniqueness and Existence of Math Objects

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