A familiar figure to these twelve-year-olds, O'Henry had come to rely on their help on tricky cases. Being a smart and serious student of puzzles himself, he characteristically started his briefing by giving the twins a small history lesson.

"There are many classic puzzles in which people either always tell the truth or always lie," he began. "You ask them questions and either you determine who is the liar or you discover some fact without explicitly determining anyone's honesty.

"For example, here is what I consider to be the queen of the classic liar problems. You are in unfamiliar country walking on a path. You encounter a single armed warrior at a fork in the road. Each branch of the fork leads to a village. You know that one road leads to a group of peaceful people who always tell the truth and will give you food. The other leads to a village of congenital liars who will kill you. The people from the two villages look alike. You are permitted one yes-or-no question to the warrior and then you must choose a fork and meet your fate. What question should you ask?"

(Think of your own answer before you read on.)

Ask, "Does this branch lead to your village?" (while pointing to one branch).

Here's why: Suppose you are pointing toward the liar's village. The liar will deny that you are pointing to his village and the truthteller will, too. If you point toward the truthtellers' village, both will say they come from there. In either case, you know which way you should go.

O'Henry continued, "The trouble is that the liars most of us know in real life are only occasional liars. Sometimes they choose to tell the truth and sometimes they lie. That might seem to make things easier, but it doesn't. If the warrior in the example were an occasional liar, he might tell you to go to his real village in response to the question.

"In fact if there were at most one occasional liar in a group of warriors while the rest told the truth, you would need at least three warriors to determine what to do using this question. The majority would tell you the truth.

"My problem concerns a crime scene, but I can't tell you the details because they are confidential, so we'll make it a game. Suppose that there is an object in an opaque box. You know it is one object and that it can be either red or black, either large or small, and either a shoe or a sock. You want to discover what's in the box.

"Three people have seen the object. At most one is an occasional liar. The others are honest."

**Problem 1.** Suppose you may ask each person at most three yes-or-no questions provided you ask a total of no more than seven questions. Can you figure out the size, color and type of object?

"Now for the more difficult problem: Six people have seen the object in the box. At most two of these people are occasional liars. The others are honest."

**Problem 2.** Can you ask each person at most two yes-or-no questions and figure out what is in the box?

**Problem 3.** How much better could you do if socks could be only black and shoes could be only large?

**Solutions:**

**1.** Cloe answered almost immediately: "Call the people A, B, C. Ask A and B about the size; if they agree, their answer is trustworthy. Ask A and B about the color; if they agree again, that answer is trustworthy, too. Ask A and B about the object, and if they agree about that, then you've solved the problem with just six questions. Now suppose that A and B disagree about their answers to any of the questions. That means either A or B is an occasional liar. Immediately pose that same question and any remaining ones to C, whose answer must be trustworthy. If A or B tells a lie about either the size or color, you can always solve the problem with a total of at most six questions. If A and B agree until the question about the object, then you will need a total of seven questions."

**2.** Call the people A, B, C, D, E, F. Ask A, B and C about size. If there is no disagreement, then ask D, E and F about color. If there is no disagreement about color, then ask any five about the type of object (sock or shoe) and trust the majority answer. This scenario with its 11 questions turns out to be the worst of all, even though nobody may ever have lied. When liars show up early on, fewer questions are needed because you can then concentrate your questioning on the truthtellers.

Because there are quite a few cases, consider this decision tree
(http://cs.nyu.edu/cs/faculty/shasha/papers/liars1.pdf) of possible responses. Start at the top node (the root) and follow each outcome as you go down the tree.

**3.** I'm not going to give you the whole solution, but consider what a scientist knowledgeable in information theory would do in this situation: address the question with greatest uncertainty first. So ask A, B and C about shoes or socks first. If you get consistency then you have only one more attribute to ask about. The other is already known. Can you take it from here?