6
$\begingroup$

Ten people are at a fancy party. The guest list includes Obama, Shaq, Captain Falcon, Jaxon, Walter White, Bob, Emma Watson, Plato, Sherlock Holmes and John Watson. Sherlock and Watson arrive late to the party, before they arrive, the other guests decide to play a party game.

The game has the following rules:

  • They decide to let Shaq go first (because he’s the best dressed)
  • Each person may give up to 2 high fives. (Once with their left and once with their right hand).
  • The game begins when Shaq gives at least one high five. Since he began the game, Shaq is not allowed to receive a high five.
  • A person may not give a high five, until they have received one. (Except for Shaq)
  • Once a person receives a high five, they may not receive another one. (From anybody with any hand).
  • The game ends when everyone has received a high five (Except for Shaq).

Sherlock and Dr. Watson arrive at the party, and are sorely disappointed that they missed the game. Anxious to find out everything they can about what they missed, they decide to interview each of the guests.

Dr. Watson decides to interview people in the following way:

  1. Anytime he interviews somebody for the first time, he will record their name.
  2. He stops interviewing when everyone’s name has been recorded.
  3. He begins with Shaq.
  4. He asks the interviewee if they gave a left high five. If they did, he finds the person they gave the left high five to, and interviews that person returning to step 4. If they gave no high fives with their left hand he proceeds to the next step.
  5. He asks the interviewee if they gave a right high five. If they did, he finds the person they gave the right high five to, and interviews that person returning to step 4. If they gave no high fives with their right hand he proceeds to the next step.
  6. He asks if they received a left, or a right high five.
  7. If they received a left high five, he finds the person from whom they received the high five and returns to step 5.
  8. If they received a right high five, he finds the person from whom they received the high five and returns to step 6.
  9. If the person did not receive a high five at all, he asks the interviewee who he gave a right high five to, and interviews that person, returning to step 4.

Still not satisfied, Sherlock asks Watson to conduct a second round of interviews following a different procedure:

  1. He begins with Shaq.
  2. He stops interviewing when everyone’s name has been recorded.
  3. Before recording a name, he checks to make sure it isn’t already on the list.
  4. He asks the interviewee if they gave a left high five. If they did, he finds the person they gave the left high five to, and interviews that person returning Step 4. If they gave no high fives with their left hand he proceeds to the next step.
  5. He records the interviewee’s name.
  6. He asks the interviewee if they gave a right high five. If they did, he asks who they gave the right high five to.
  7. If they gave a right high five to a person who is not already on the list, he finds the person they gave the right high five to, and interviews that person returning to Step 4.
  8. If they did not give a right high five or they gave a right high five to somebody already on the list then he records the name of the person from whom they received their high five, and he interviews that person returning to step 6.

After Watson has finished conducting his interviews, he shows his lists to Sherlock Holmes. The first list reads:

Shaq, Captain Falcon, Walter White, Jaxon, Emma Watson, Obama, Bob, Plato

The second list reads:

Walter White, Emma Watson, Jaxon, Captain Falcon, Obama, Shaq, Plato, Bob

Sherlock examines the lists for a few moments, turns to his friend and says: “It is elementary, my dear Watson”.

Using only these lists, and his knowledge of the process, Sherlock can tell exactly who high fived who and with which hand.

Can you?

$\endgroup$
  • $\begingroup$ There are two knrumsey's. Multiple personality disorder? $\endgroup$ – Rand al'Thor Apr 4 '15 at 10:08
  • 2
    $\begingroup$ Lateral thinking answer: when it says "Sherlock and Watson arrive late", it actually means Emma Watson, not John Watson! $\endgroup$ – Rand al'Thor Apr 4 '15 at 10:49
4
$\begingroup$

Shaq: left to Captain, right to Bob
Captain: left to Walter, right to Obama
Walter: right to Jaxon
Jaxon: left to Emma
Bob: left to Plato
[No other high fives.]

Although it doesn't have to be solved this way, it helps to realize that the pattern of high fives forms a binary tree. Then figure out that the first list is a pre-order traversal and the second is an in-order traversal.
The first element of the first list (S,C,W,J,E,O,B,P) tells us that Shaq is the root. The position of Shaq in the second list (W,E,J,C,O,S,P,B) tells us that (W,E,J,C,O) came from his left high five and (P,B) from his right. Now split the first list the same way: (C,W,J,E,O) and (B,P). The first element of (C,W,J,E,O) tells us that Shaq's left high five went to Captain. Splitting the first part of the second list (W,E,J,C,O) on Captain tells us that his left high five went to (W,E,J) and his right to (O). Continuing in this way gives the solution above.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.