Presidential Logic

Date: 10/28/2002 at 11:22:18
From: Sam
Subject: Math problem of the week

A history test has three questions on Presidents of the United States. 
Here are the answers six students give.

 1. Polk, Polk, Taylor
 2. Taylor, Taylor, Polk
 3. Filmore, Filmore, Polk
 4. Taylor, Polk, Filmore
 5. Filmore, Taylor, Taylor
 6. Taylor, Filmore, Filmore

Every student has at least one correct answer. What are the answers?

Date: 10/28/2002 at 16:16:21
From: Doctor Ian
Subject: Re: Math problem of the week

Hi Sam,

Interesting question! 

Let's start by lining things up (and abbreviating the names), so if
there are any patterns, they'll be easier to find:

   P P T   
   T T P   
   F F P  
   T P F  
   F T T  
   T F F  

Now, let's look at all the possible answer keys:

   F -> FF -> FFF          
              FFP
              FFT

        FP -> FPF
              FPP
              FPT

        FT -> FTF
              FTP
              FTT

   P -> PF 
        PP   etc.
        PT
   
   T -> TF
        TP   etc.
        TT

(All I've done here is start with the possible choices for the first
answer - F, P, or T - and then extend each of those with the possible
choices for second and third answers. I've left the final 2/3 for you
to expand.) 

Now let's check the answer key FFF against the students' answers:

   F F F   Correct
   - - -   -------
   P P T      0
   T T P      0
   F F P      2
   T P F      1
   F T T      1
   T F F      2

So this clearly can't be the key, because the first two students 
didn't get any right. How about FFP? 

   F F P   Correct
   - - -   -------
   P P T      0
   T T P      1
   F F P      3
   T P F      0
   F T T      1
   T F F      1

Nope, it's not that one either.  

If you generate all the rest of the keys and test them against the
answers this way, you should find only one key for which every student
gets at least one answer right. 

Or you could try to be clever. For example, by making T the first
answer, you make sure that at least half of the students get one 
right:

   T       Correct
   - - -   -------
   P P T      
   T T P      1
   F F P      
   T P F      1
   F T T      
   T F F      1

Let's rearrange the students so we can concentrate on the ones who
haven't got any right yet:

   T       Correct
   - - -   -------
   T T P      1
   T P F      1
   T F F      1
   P P T      
   F F P      
   F T T      

By making the final answer T, we can get two more students. And then
it's just a matter of getting the remaining student to be right on the
second question.

Now, this can lead us to _an_ answer, but is it the _only_ answer? The 
first method I outlined is tedious, but if you check every possible 
answer key, you'll find every possible set of answers that will 
satisfy the problem. The second method is much easier, but we don't 
have any idea whether the solution it finds is unique.  

That's one of the trade-offs that you often have to make make when you
decide to be clever.

I hope this helps. Write back if you'd like to talk more about this,
or anything else. 

- Doctor Ian, The Math Forum
  http://mathforum.org/dr.math/