0.2 Discrete structures problem solving  (Page 2/6)

Some helpful tips

There is no single method that works for all problems. However, there is a wealth of heuristics we can try. Following are some of the often used heuristics. Add your own heuristics as you gain experience.

(1) Have I seen it before?

That is, do I know similar or related problems? Similar/related problems are ones with the same or a similar unknown or unknown may be different but the settings are the same or similar.

(2) Do a little analysis on relationships among data, conditions and unknowns, or between hypothesis and conclusion.

(3) What facts do I know related to the problem on hand?

These are facts on the subjects appearing in the problem. They often involve the same or similar words. It is very important that we know inference rules.

(4) Definitions: Make sure that you know the meaning of technical terms. This is obviously crucial to problem solving at any level. But especially at this level, if you know their meaning and understand the concepts, you can see a solution to most of the problems without much difficulty.

(5) Compose a wish list of intermediate goals and try to reach them.

(6) Have you used all the conditions/hypotheses? When you are looking for paths to a solution or trying to verify your solution, it is often a good idea to check whether or not you have used all the data/hypotheses. If you haven't, something is often amiss.

(7) Divide into cases: Sometimes if you divide your problem into a number of separate cases based on a property of objects appearing in the problem, it simplifies the problem and clear your mind. For example if the problem concerns integers, then you may want to divide it into two cases: one for even numbers and the other for odd numbers as. (8) Proof by contradiction: If you make an assumption, and that assumption produces a statement that does not make sense, then you must conclude that your assumption is wrong. For example, suppose that your car does not start. A number of things could be wrong. Let us assume for simplicity's sake that either the battery is dead or the starter is defective. So you first assume that the battery is dead and try to jump start it. If it doesn't start, you have a situation that does not make sense under your assumption of dead battery. That is, a good battery should start the car but it doesn't. So you conclude that your assumption is wrong. That is the battery is not the cause. Proof by contradiction follows that logic.

In this method we first assume that the assertion to be proven is not true and try to draw a contradiction i.e. something that is always false. If we produce a contradiction, then our assumption is wrong and therefore the assertion we are trying to prove is true.When you are stuck trying to justify some assertion, proof by contradiction is always a good thing to try.

(9) Transform/Restate the problem, then try (1) - (3) above.

(10) Working backward: In this approach, we start from what is required, such as conclusion or final (desired) form of an equation etc., and assume what is sought has been found. Then we ask from what antecedent the desired result could be derived. If the antecedent is found, then we ask from what antecedent that antecedent could be obtained. ... We repeat this process until either the data/hypotheses are reached or some easy to solve problem is reached.