Problem Solving and Problem Solving Exercises

 

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 Car is engineer. Then you must number the statements in your essay and create a structure diagram.

Here is a sample essay.

5<Carr cannot be the pilot> because 4<Carr earns more than the pilot>. 6<Carr cannot be the copilot> because 2<the copilot earns the least>, and 4<Carr earns more than the pilot>. Since 0<each person has exactly one job>, it follows that 7<Carr must be the engineer>. Since 7<Carr is the engineer>, 8<Brown cannot be the engineer>. 9<Brown cannot be the copilot> either because 1<the copilot was an only child> and 3<Brown has a sister.> So 0<by the fact that each man has exactly one job,> 10<Brown must be the pilot,> and so 11<the copilot job goes to Allen.>

Here is a diagram for this essay.



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:
 




Homework Due Feb. 23

Instructions for these problems. Solve the following 4 problems, using the matrix method. (Hint. Read carefully what the question is.) Write a clear argument explaining the reasons for your conclusion. You will need to add new sentences to fill in the reasoning. Using the new sentences and the statements given in the original problem, create a diagram showing the structure of your reasoning.



 

Problem #1:
0. Four married couples are eating together in a restaurant. In alphabetical order, the husband's names are Gerald, John, Michael and Tom. The wives are Ann, Betty, Carol, and Pat.
1. Ann is married to Michael.
2. Carol is John's sister.
3. Tom and Carol were once engaged.
4. Pat has four brothers, but,
5. her husband is an only child.

Who is married to Betty?

Solution:
 
 
Gerald John Michael Tom
Ann   No  since Michael is married to Ann YES 2)  
Betty   YES    
Carol   No  2)    
Pat   No  2) and 5)    

Essay:

Since 1<Ann is married to Michael>, 6<she can't be married to John>.  2<Carol is John's sister>, so 7<Carol can't be married to John>.  8<John is not an only child> because 2<Carol is his sister>.  But 5<Pat's husband is an only child>.  Therefore 9<John can't be married to Pat>.  So 10<John can't be married to Ann, Carol or Pat>, and 11<Betty is the only woman left>.  So 12<John is married to Betty>.

Diagram:



Problem 2 : (from IR pp. 66-67, Exercise 15)
0. On a certain train, the crew consists of the brakeman, the fireman, and the engineer. Their names listed alphabetically are Jones, Robinson and Smith. On the train are also three passengers with corresponding names: Mr. Jones, Mr. Robinson, and Mr. Smith. The following facts are known.
a. Mr. Robinson lives in Detroit.
b. The brakeman lives halfway between Detroit and Chicago.
c. Mr. Jones earns exactly $50,000 a year
d. Smith once beat the fireman at billiards
e. The brakeman's next-door neighbor, one of the three passengers mentioned earns exactly three times as much as the brakeman
f. The passenger living in Chicago has the same name as the brakeman.

Who is the engineer?

Essay:

According to (e), the brakeman's neighbor earns exactly 3 times as much as the brakeman.  So 1<if Mr, Jones is the brakeman's neighbor, then Mr. Jones must earn exactly three times what the brakeman makes>. But (c) says that Mr. Jones earns exactly $20,000 2<an amount that is not exactly 3 times anything>.  So 3<Mr. Jones could not be the brakeman's neighbor.>  We can also show that the 4<brakeman's neighbor is not Mr. Robinson>.  The reason is that (b) the brakeman's neighbor lives halfway between Detroit and Chicago, but (a) Mr. Robinson lives in Detroit.  Sentence (e) also makes it clear that 5<the brakeman's neighbor is one of the three passengers>.  Since 6<Mr. Smith is the only passenger left>, 7<he must be the brakeman's neighbor>, and so 8<he must live halfway between Detroit and Chicago>.  It follows that 9<Mr. Smith does not live in Chicago>.  We know that (f) the passenger living in Chicago has the name of the brakeman, which means 10<one of the passengers must live in Chicago>.  As we already saw (a) Mr. Robinson lives in Detroit, not Chicago, and since 9<Mr. Smith doesn't live in Chicago> either, 11<the passenger that lives in Chicago must be Mr. Jones>.  So by (f), 12<the person with same name (namely Jones) must be the brakeman>.  Since 0<no person on a train crew has two jobs>, it follows that 13<Smith is not the brakeman>.  14<He is not the fireman> either because (d) says that Smith beat the fireman at billiards.  We know that 0<Smith has one of the jobs>, and 15<the only job left is engineer>.  So 16<Smith is the engineer>.

Diagram:
 



Problem #3 (from IR, p. 62, Ex. 1)

0. In a certain mythical community politicians never tell the truth, and non-politicians always tell the truth. 1. A stranger meets three natives and asks the first of them "are you a politician?" 2. The first native answers the question. 3. The second native then reports that the first native denied being a politician. 4. The third native says that the first native is a politician.

How many of these natives are politicians?

Essay:

1[Native 1 answered the question: "are you a politician?"].  Now 2[if she is a politician, she would have to say she was a non-politician] because 3[politicians never tell the truth].  4[If she was a non-politician, she would also have to say she was a non-politician], because 5[non-politicians always say the truth].  Either way, 6[native 1 said she was a non-politician].  This means that 7[native 2 was right when she said that the first native denied being a politician].  So since 3[politicians never tell the truth], 8[native 2 must be a non-politician].  Now 9[ if native 1 really is a politician, native 3 would be right] because 10[3 says 1 is a politician.]  Furthermore, 11[if 3 is right, 3 is a nonpolitician.]   So 12[if 1 is a politician, then 3 is not one.]  On the other hand, 13[if 1 is not a politician, then what 3 said is wrong]  and 14[if 3 is wrong, then 3 must be a politician].   So 15[if 1 is not a politician, then 3 is one.]  It follows that 16[between 1 and 3 there must be exactly one politician].  We already showed that 8[2 is a non-politician], so it follows that 17[there is exactly one politician].

Diagram:
 



Problem # 4. (from IR, p. 66, Ex. 13)

0. Alice, Betty, Carol, and Dorothy are either a lifeguard, a lawyer, a pilot, or a professor. 1. Each wore a white, yellow, pink or blue dress. 2. The lifeguard beat Betty at canasta, and 3. Carol and the pilot often played bridge with the women in pink and blue dresses. 4.Alice and the professor envied the woman in the blue dress, 5. but this was not the lawyer, 6. as she always wore a white dress.

What was each woman's occupation and dress color?

Essay:

It says 6) the lawyer wore the white dress, so the pilot does not wear white.  We also know that the pilot wears neither blue nor pink, since 3) the pilot plays bridge with the people in these dresses.  The only dress left for the pilot is yellow, so the pilot wears yellow.  The remaining dresses are pink and blue.  But the professor does not wear blue because 4) she envied the woman in blue.  So the professor gets pink and the lifeguard gets blue. Now that we know what dresses go with which occupations, we can figure out the names.  Carol doesn't wear pink or blue, because it says 3) she played bridge with people wearing these dresses.  So Carol is neither the professor nor the lifeguard.  She is not the pilot either since 3) she and the pilot played bridge.  The only remaining occupation for Carol is lawyer, so Carol is the lawyer.  This means that Alice is not the lawyer.  She also is not the professor because 4) she and the professor envied the woman in the blue dress.  From the same fact it follows that Alice doesn't wear a blue dress, which means she is not the lifeguard.  The only remaining occupation is pilot, so Alice is the pilot.  We know who lawyer and pilot are, so Betty must be either a lifeguard or a professor.  She can't be the lifeguard, since 2) the lifeguard beat her at canasta.  So Betty is the professor, leaving Dorothy to be the lifeguard.  So to summarize we have:
Alice is the pilot wearing yellow; Betty is the professor wearing pink;
Carol is the lawyer wearing white; Dorothy is the lifeguard wearing blue.

You may omit the diagram for this problem.