0.2 Discrete structures problem solving  (Page 5/6)

Devising a Solution Plan: For this problem, let us try "proof by contradiction". When you are asked to prove the impossibility of an event or non-existence of certain things, this approach often is quite helpful.

Following the "proof by contradiction", let us assume that the conclusion is false, that is the equation ax2 + bx + c = 0 has a rational root m/n, where m and n are integers, when a, b, and c are odd integers. We can assume without loss of generality that m and n do not have any factors in common. Then

a(m/n)2 + b(m/n) + c = 0 . ------------------------ (1)

Let us try to derive a contradiction from this. First let us make this equation simpler, that is, let us get rid of fractions.

Since n is not equal to 0, multiplying the both sides of (1) by n2, we get

am2 + bmn + cn2 = 0. ------------------------ (2)

Since m is an integer, it is either even or odd. We are going to consider those cases one by one. That is "divide into cases".

Let us first consider the case when m is even. Then n is odd, since otherwise m and n have a common factor 2. Now am2 + bmn is even, and cn2 is odd. Hence am2 + bmn + cn2 can not be 0.

Next let us consider the case when m is odd. By an argument similar to the previous case, we can see that n is also odd. If m and n are odd, then am2, bmn, and cn2 are all odd, since a, b, and c are odd integers. However, the sum of three odd numbers can not be equal to 0.

Thus by assuming that the conclusion is false, we have arrived at a contradiction, that is m/n does not satisfy the equation. Hence our assumption must be wrong, and therefore the conclusion is correct.

Example 4

This is another proof type problem and "working backward" technique is used.

Problem: Prove that ( a + b + c )2 ≤ 4(ab + bc + ca) , if a, b, c are three sides of a triangle. Understanding the Problem: This is a "prove" type problem.

The hypothesis is that a, b, and c are three sides of a triangle, and the conclusion is that inequality ( a + b + c )2 ≤4( ab + bc + ca ) holds.

Devising a Solution Plan: Here we try "Working Backward" heuristic. That is manipulate the conclusion possibly using the hypothesis and reduce it into something that is obviously true.

First by multiplying out the left hand side of the inequality, ( a + b + c )2 = a2 + b2 + c2 + 2(ab + bc + ca).

Hence if a2 + b2 + c2 ≤ 2(ab + bc + ca) , then the conclusion holds.

Next, to see what we can try, note that we have not used the hypothesis yet, and see if it can help here.

It is well known that the sum of two sides of a triangle is greater than the third side. Hence a + b>c , b + c>a , and c + a>b hold.

From these we can obtain c(a + b)>c2 , a(b + c)>a2 , and b(c + a)>b2.

By adding these three inequalities, we get

a2 + b2 + c2<a(b + c) + b(c + a) + c(a + b) = 2(ab + bc + ca).

Hence a2 + b2 + c2<2(ab + bc + ca).

Hence a2 + b2 + c2 ≤ 2(ab + bc + ca).

Hence ( a + b + c )2 ≤4(ab + bc + ca) holds.

Example 5

This is a find type problem and "working backward" technique is used.

Problem: Given a 4 quart pail and a 9 quart pail, obtain 6 quarts of water in the 9 quart pail using these two pails. You can fill or empty the pails and you can have as much water as you want.