Lecture Notes on Problem Solving


I.  Why  Do a Unit on Problem Solving?

 A.  Practice problems found on GRE, MCAT, LSAT?
 B.  Strengthen understanding of argument structure by diagramming   your OWN reasoning.
 C.  Create essays from structure diagrams.

II.   The Structure of Problem Solving

 Reasons             These describe the problem.
        :
 ________
 Conclusion        This gives the solution.

 Example:

 5 are coming to dinner.
 The recipe serves 3.      What adjustment must be made to the recipe?
 ________________
 Multiply the amounts by 5/3 = 1 and 2/3 = a scant double.

III.  3 Kinds of Problems

 A.  Unsolvable.  (No solution)
  What happens when an irresistible force meets an immovable  object?
  What household chemicals can you mix together to get an elixir  of life?
 B.  Closed.  (Exactly ONE solution)
  What is the smallest prime greater than 7?
 C.  Open.  (Many acceptable solutions)
  How can I seat 4 married couples at a dinner table so that the   neighbors of each person are of opposite sex?
 D.  Optimized.  (Many acceptable solutions, but we want the best.)
  What is the best way to  get from downtown to AstroWorld?

IV.  Problem Solving Tools

 A.  Brainstorming.
  Creative and relaxed exploration of possible solutions, without criticism.

 B.  Organizing.
  1.  Methods that find a (the) solution once set of possible solutions is determined.
  2.  Techniques for verifying the correctness of a solution.
  3.  Ways of presenting the solution clearly to others.
 
 
 

A Sample Solved Problem:

0. In a certain flight crew the positions of the pilot, copilot and flight engineer are held by Allen Brown and Carr, though not necessarily in that order. 1. The copilot was an only child and 2. he earns the least. 3. Carr married Brown's sister and 4. earns more than the pilot.
Who is the copilot?

To help solve the problem lay out a diagram of all possible combinations:

Now use the information given to rule things out. For example, 4. entails that Carr is not the pilot. So we can eliminate that combination.

Now 2 tells us that the copilot earns the least. But 4 means that Carr does not earn the least. So Carr can't be the copilot. Since there are 3 men and 3 jobs, Carr must be the engineer.

But if Carr is the engineer and each man has one job, neither Allen nor Brown can be engineer.

1 tells us that the copilot was an only child, but 3 means that Brown can be an only child. So Brown can't be the copilot. That means Allen is the only one left who could be the copilot. So Allen is not the pilot, and Brown is.

Filling out the matrix to solve the problem is not all you are asked to do for these exercises. You must then create an essay that consists of an argument whose conclusion is the solution: Allen is copilot; Brown is pilot; and Carr is engineer. Then you must number the statements in your essay and create a structure diagram.

Notice that the reasoning to support the idea that Allen is the copilot can be simplified.  Eliminating Brown as copilot  (using 1 and 3) and Carr as copilot (by 2,4) is enough to support the conclusion that Allen is the copilot.  Often, once you have worked out the solution by a matrix you can see a simpler way to argue for the solution.

Here is a sample essay.  Obviously there are many, many equally good essays and diagrams.

5<Carr cannot be the copilot> because 2<the copilot earns the least>, and 4<Carr earns more than the pilot>. 6<Brown cannot be the copilot> either because 1<the copilot was an only child> and 3 tells us that 7<Brown has a sister.> Since 0<each man has exactly one job> 8<Allen is the only person left who can be copilot> so 9<the copilot is Allen.>

Here is a diagram for this essay.

(2+4)->5
(1+7)->6
3->7
(5+6+0)->8->9

Now you try one for practice (not for homework). Here is an example from (IR p. 63 Ex. #3). Note that this will require a lot more creativity in applying the matrix method.

0) Mr. Short, his sister, his son, and his daughter are fond of golf and often play together.

The following statements are true of their foursome:

1) The best's player's twin and the worst player are of opposite sex.

2) The best player and the worst player are of the same age.

Which one of the foursome is the best player?

Solution:

By 1), we know that Best's Twin and Worst are not the same, and clearly Best and Best's Twin are different also. So we can lay out three distinct roles in a matrix.
 
Mr. Short Mr. S's Sister Mr. S's Son Mr. S's Daughter
Best        
Best's Twin        
Worst        

For starters here are some things you can deduce from what we know:

3) Twins have the same age.

So 4) the only possible twins are Mr. S. - Sister and Son - Daughter.

So 5) the twins are of opposite sex.

So 6) Best is same sex as Worst. (by 1).

The most interesting facts here seem to be 2) and 6)  Best and Worst are the same age and sex.  But even with this information we can make no headway on filling in the matrix.  In a situation like this it is a good idea just to suppose one possible solution and see where it leads.  So lets suppose that Mr. Short is Best.  Then the matrix can be filled in as follows:
 
Mr. Short Mr. S's Sister Mr. S's Son Mr. S's Daughter
Best Suppose      
Best's Twin        
Worst     YES by 6)
NO by 2)!		  

You can see there is a problem.  Because Best and Worst are the same sex, then supposing that Best is Mr. S. guarantees that Worst is his Son.  But Worst can't be his son because then Mr. S. and his son would be the same age which is impossible.  So Mr. S. cannot be Best.  Let us see what happens when we suppose that Mr. S's Sister is Best.  Again we find a problem.
 
Mr. Short Mr. S's Sister Mr. S's Son Mr. S's Daughter
Best   Suppose    
Best's Twin YES by 3)      
Worst       YES by 6)
NO by 2)!

We run into a similar problem, but the argument is more complicated.  If Sister is Best, then since Best and Worst are the same sex, it follows that Daughter is Worst.  But then Daughter must be the same age as Sister.  Now in general a Daughter and Sister of a man can be the same age.  But not in this case, for we also know that twins are of opposite sex, which ensures that Mr. Short is Sister's twin.  This means that Sister is the same age as Mr. S, who is the father of the Daughter.  It follows that the Daughter and the Sister cannot be the same age.   So assuming Sister is Best leads to a problem and it follows that Sister is not Best.
 
Mr. Short Mr. S's Sister Mr. S's Son Mr. S's Daughter
Best     Suppose  
Best's Twin       YES by 3)
Worst YES by 6)
NO by 2)!		      

What happens if we assume that Son is Best?  Then Mr. Short is the only person who could be Worst, since Best and Worst are the same sex.  But then Mr. S. and his Son would be the same age, which is impossible.  So Son cannot be Best.   The only remaining possibility is that the Daughter is Best.  The diagram below shows how this is (just barely) possible.  On this assumption Son and Daughter are twins, Daughter is Best and Sister is Worst.  It is possible for a Sister and Daughter to be the same age, so the solution fits.
 
Mr. Short Mr. S's Sister Mr. S's Son Mr. S's Daughter
Best       Suppose
Best's Twin     YES by 3)  
Worst   YES by 6)    

The conclusion is that the Daughter of Mr. S. is the Best golfer.

An Essay.

7<The Daughter of Mr. S. is the best golfer> because 8<none of the other members of the foursome could possibly qualify.>  To prove this, we need first to develop some facts about the Best and Worst golfers.  Since 3<twins have the same age>, 4<the only possible twins are Mr. S. and his Sister, and the Son and Daughter>.  So 5<the twins are of opposite sex>. Since 1<the Best  player's Twin and Worst player are of opposite sex>, we know that 6<the Best and Worst players are the same sex>.  Now we are ready to show that 8<no one except the Daughter could be the Best golfer>. 9<If Mr. Short were the Best golfer then his Son would have to be the Worst>, since 6<Best and Worst are the same sex> and 10<the other members of the foursome are female>.  But because 2<the Best and Worst golfers have the same age>, it follows that  11<if Mr. Short's Son is Worse then the Son and his father would have to be the same age>, and 12<this is impossible>.  So 13<Mr. Short cannot be the Best golfer.>  14<The son can be rulled out as well>, for similar reasons.  Since 6<Best and Worst are the same sex>, 15<if the Son is Best, then Mr. Short must be the Worst>.  But  16<if Mr. Short is Worst  then Mr. Short and his Son are the same age> because 2<the Best and the Worst are the same age>.  But 17<Mr. Short and his son can't be the same age>.  So 14<The Son cannot be Best>.  Finally 18<we can rule out the Sister>.  19<If the Sister is the Best, then the Best player's Twin could only be Mr. Short>, because we said that 4<the only possible twins are Mr. S. and his Sister and the Son and Daughter>.   It follows that 20<if the Sister is Best, then the Sister and Mr. Short are the same age>.  But 6<the Best and Worst are the same sex> as well, so 21<if the Sister is Best the Daughter must be Worst> and since 2<the Best and the Worst are the same age>, 22<if Sister is Best, then she must be the same age as the Daughter>.  But 23<she can't be the same age as the Daughter> since 24<this would mean that Mr. Short, and is Daugher would be the same age>.  It follows that 18<the Sister cannot be Best>.  0<One of the foursome must be the Best golfer>  But 8<we have just ruled out everyone except the Daughter>.  So 7<the Daughter is the Best golfer.>

Diagram: