Tuesday, December 9, 2014

A Star Trek Logic Puzzle [Updated]

♪Which one does not belong?♪
Yesterday I came across a cool logic puzzle at io9. They reproduced it from the website of Raphael Finkel, a professor in the Computer Science Department at the University of Kentucky. I am constitutionally unable to refrain from solving a logic puzzle; moreover, the puzzle uses characters from Star Trek: The Next Generation, which has nothing to do with the solution, but I'm superficial like that.

Here is the problem, for which I take no credit, quoted from io9 and Professor Finkel's web page (but don't look at the latter unless you want to see the solution):

Grobly Grizik is planning to write a novel fashioned after Star Trek: The Next Generation. In this novel, six of the crew members compete both at Fizzbin and at Tridimensional chess. Each crew member gets two independent rankings for ability at these games, with 1 ranked lowest and 6 highest. Every crew member has a personal hero among the crew, and every crew member is afraid of some crew member. Everyone is the hero of somebody, and everyone is feared by somebody. Nobody either fears him/herself nor counts him/herself as a hero. Nobody fears his/her own hero. From the given clues, discover every crew member's ranking at Fizzbin and at Tri-D chess, as well as whom he/she fears and whom he/she counts as a hero:
  1. Geordi ranks 2 at Tri-D Chess.
  2. Picard ranks two positions behind Troi at Fizzbin.
  3. Troi is feared by the person Geordi fears.
  4. Worf's hero ranks 3 times lower at Tri-D Chess than the crew member who is best at Fizzbin.
  5. Picard's hero fears Geordi.
  6. Data's hero is not Geordi.
  7. Data is the hero of Riker's hero.
  8. The person who is worst at Fizzbin is better than Troi at Tri-D Chess.
  9. The person ranked number 3 at Tri-D Chess is ranked 4 positions higher than Data at Fizzbin.
  10. Riker is feared by the person Picard fears and is the hero of Worf's hero.
  11. Riker is ranked 2 lower at Tri-D Chess than the crew member ranked 2 at Fizzbin.
Solution

Upon closer examination, we find that there are five statements dealing with only heroes or fear (Statements 3, 5, 6, 7, 10), five statements dealing with only Tri-D Chess or Fizzbin (Statements 1, 2, 8, 9, 11), and exactly one statement dealing with both (Statement 4). Let's renumber, and also break up Statement 10:

1A. Troi is feared by the person Geordi fears.
1B. Riker is feared by the person Picard fears
1C. Picard's hero fears Geordi.
1D. Riker is the hero of Worf's hero.
1E. Data is the hero of Riker's hero.
1F. Data's hero is not Geordi.

2. Worf's hero ranks 3 times lower at Tri-D Chess than the crew member who is best at Fizzbin.

3A. Picard ranks two positions behind Troi at Fizzbin.
3B. The person who is worst at Fizzbin is better than Troi at Tri-D Chess.
3C. The person ranked number 3 at Tri-D Chess is ranked 4 positions higher than Data at Fizzbin.
3D. Riker is ranked 2 lower at Tri-D Chess than the crew member ranked 2 at Fizzbin.
3E. Geordi ranks 2 at Tri-D Chess.

The puzzle of fears and heroes can be solved on its own, using only Statements 1A – 1F. The fact that each crew member is feared by some other member means that the correspondence is surjective; therefore, it must be bijective as well, and each must be feared by exactly one other member. So we can't have two members fearing the same member, etc. The same goes for heroes.

First, for fears, Statement 1A yields
F: Geordi → (???) → Troi 
and Statement 1B yields
F: Picard → (???) → Riker
For heroes, Statements 1D and 1E yield
H: Worf → (???) → Riker → (???) → Data
Now, Data must adulate someone. He could* possibly adulate Riker or Worf, if we had one of the following arrangements:
H: Worf → Data → Riker → Worf
H: Worf → (???) → Riker → (???) → Data → Worf
Both are compatible with the preceding. The latter leaves out a single crew member, because the unknowns can't be any of the three already listed, and, since no one can adulate themselves, this is impossible, leaving us with the former. But this would imply one of the following:
H: Picard → Troi → Geordi → Picard
H: Picard → Geordi → Troi → Picard
But both are impossible, because both violate 1C (Troi cannot both fear and adulate Geordi, and Geordi cannot fear himself).

So Data adulates neither Worf nor Riker, hence must adulate a third unknown, who in turn adulates Worf, so that we have
H: Worf → (???) → Riker → (???) → Data → (???) → Worf
where the three unknowns must be Picard, Troi, and Geordi. Statement 1F states that Data doesn't adulate Geordi, so Data must adulate Picard or Troi. If Picard, then Statement 1C implies that Worf fears Geordi. This would give us
F: Worf → Geordi → (???) → Troi
F: Picard → (???) → Riker
Five crew members are written explicitly here. So at least one of the unknowns already appears in one of these chains, and the only way the two chains fit together is if Picard is feared by Geordi, so
F: Worf → Geordi → Picard → Troi → Riker
But this creates an impossible situation. Worf must adulate Geordi or Troi. If Geordi, then this violates his fear of Geordi, since no one can both adulate and fear the same person. If Troi, then Troi would adulate Riker, violating her fear of Riker.

It follows that Data adulates Troi. We have
H: Worf → (???) → Riker → (???) → Data → Troi → Worf
Now, either Worf adulates Picard and Riker, Geordi, or vice versa. But Worf can't adulate Picard, or else Picard would adulate Riker, with the implication that Riker would fear Geordi (Statement 1C), resulting in
F: Picard → (???) → Riker → Geordi → (???) → Troi
which violates Riker's adulation of Geordi. So Worf adulates Geordi, and Riker, Picard. We've completed our hero chain:
H: Worf → Geordi → Riker → Picard → Data → Troi → Worf
Next, Statement 1C implies that Data fears Geordi, so we have
F: Data → Geordi → (???) → Troi 
F: Picard → (???) → Riker
The only way for these chains to fit together is for Picard to be the first unknown. So we have
F: Data → Geordi → Picard → Troi → Riker → Worf → Data
This completes our chain of fear. On to Tri-D and Fizzbin.

According to Statement 3A, Picard ranks 2 lower than Troi at Fizzbin, so he can't rank 5 or 6, and Troi can't rank 1 or 2. Similarly, Troi can't rank 6 at Tri-D (Statement 3B), and Data can't rank 3 at Tri-D or 3, 4, 5, or 6 at Fizzbin (Statement 3C); since Picard can't rank 5 or 6 at Fizzbin, Statement 3C also implies that Picard can't rank 3 at Tri-D. Also, Riker can't rank 5 or 6 at Tri-D (Statement 3D). Finally, we know for a fact that Geordi ranks 2 at Tri-D (Statement 3E). So far we have:
       |   Tri-D   | |  Fizzbin  |
       |1|2|3|4|5|6| |1|2|3|4|5|6|
  Data | |X|X| | | | | | |X|X|X|X|
Geordi |X|O|X|X|X|X| | | | | | | |
Picard | |X|X| | | | | | | | |X|X|
 Riker | |X| | |X|X| | | | | | | |
  Troi | |X| | | |X| |X|X| | | | |
  Worf | |X| | | | | | | | | | | |
(Excuse my crappy table; I have time to work out logic puzzles, but not to learn how to make tables in html.) We know that Geordi is Worf's hero, so Geordi is ranked 3 times lower at Tri-D Chess than the crew member who is best at Fizzbin. Since we already know Geordi is ranked 2, the person who is best at Fizzbin must also be best at Tri-D. This eliminates Data and Picard from being best at Tri-D, and Geordi, Riker, and Troi from being best at Fizzbin. So Worf must be best at both. Worf does not rank 2 at Fizzbin, so Statement 3D implies that Riker does not rank 4 at Tri-D.
       |   Tri-D   | |  Fizzbin  |
       |1|2|3|4|5|6| |1|2|3|4|5|6|
  Data | |X|X| | |X| | | |X|X|X|X|
Geordi |X|O|X|X|X|X| | | | | | |X|
Picard | |X|X| | |X| | | | | |X|X|
 Riker | |X| |X|X|X| | | | | | |X|
  Troi | |X| | | |X| |X|X| | | |X|
  Worf |X|X|X|X|X|O| |X|X|X|X|X|O|
Now, Riker ranks either 1 or 3 at Tri-D. If he ranks 1, then Troi must rank 3. It would follow that Troi ranks 4 places above Data at Fizzbin (Statement 3C). With the spaces available, the only way this could happen is for Data to rank 1 at Fizzbin and Troi to rank 5. But Statement 3D would imply that Troi ranks 2 at Fizzbin, a contradiction.

So Riker ranks 3 at Tri-D. He therefore ranks 4 places above Data at Fizzbin, placing Data at 1 and Riker at 5. We now know that Data did better than Troi at Tri-D (Statement 3B), so he can't rank 1 at Tri-D, and Troi can't rank 5 at Tri-D. We have:
       |   Tri-D   | |  Fizzbin  |
       |1|2|3|4|5|6| |1|2|3|4|5|6|
  Data |X|X|X| | |X| |O|X|X|X|X|X|
Geordi |X|O|X|X|X|X| |X| | | |X|X|
Picard | |X|X| | |X| |X| | | |X|X|
 Riker |X|X|O|X|X|X| |X|X|X|X|O|X|
  Troi | |X|X| |X|X| |X|X| | |X|X|
  Worf |X|X|X|X|X|O| |X|X|X|X|X|O|
Statement 3D implies that the person who ranks 2 at Fizzbin also ranks 5 at Tri-D; this means that Data does not rank 5 at Tri-D, hence must rank 4.
       |   Tri-D   | |  Fizzbin  |
       |1|2|3|4|5|6| |1|2|3|4|5|6|
  Data |X|X|X|O|X|X| |O|X|X|X|X|X|
Geordi |X|O|X|X|X|X| |X| | | |X|X|
Picard | |X|X|X| |X| |X| | | |X|X|
 Riker |X|X|O|X|X|X| |X|X|X|X|O|X|
  Troi | |X|X|X|X|X| |X|X| | |X|X|
  Worf |X|X|X|X|X|O| |X|X|X|X|X|O|
So Troi is ranked 1 at Tri-D, and Picard is ranked 5. It follows that Picard is ranked 2 at Fizzbin (Statement 3D), and Troi is ranked 4 (Statement 3A). Geordi must therefore rank 3 at Fizzbin.
       |   Tri-D   | |  Fizzbin  |
       |1|2|3|4|5|6| |1|2|3|4|5|6|
  Data |X|X|X|O|X|X| |O|X|X|X|X|X|
Geordi |X|O|X|X|X|X| |X|X|O|X|X|X|
Picard |X|X|X|X|O|X| |X|O|X|X|X|X|
 Riker |X|X|O|X|X|X| |X|X|X|X|O|X|
  Troi |O|X|X|X|X|X| |X|X|X|O|X|X|
  Worf |X|X|X|X|X|O| |X|X|X|X|X|O|
And we're done. To sum up:
  • Data fears Geordi, adulates Troi, ranks 4 at Tri-D, and ranks 1 at Fizzbin.
  • Geordi fears Picard, adulates Riker, ranks 2 at Tri-D, and ranks 3 at Fizzbin.
  • Picard fears Troi, adulates Data, ranks 5 at Tri-D, and ranks 2 at Fizzbin.
  • Riker fears Worf, adulates Picard, ranks 3 at Tri-D, and ranks 5 at Fizzbin.
  • Troi fears Riker, adulates Worf, ranks 1 at Tri-D, and ranks 4 at Fizzbin.
  • Worf fears Data, adulates Geordi, ranks 6 at Tri-D, and ranks 6 at Fizzbin.
Updated to correct an error brought to my attention by Robbie Gonzalez, who runs the puzzle column at io9 where this puzzle was featured.

* As pointed out by a correspondent with the infernal name of TartarosFalling, who wrote to correct a lacuna at this point.

3 comments:

  1. How about this solution:

    Geordie: Fizz-5, TriD-2
    Picard: Fizz-4, TriD-1
    Troi: Fizz-6, TriD- 3
    Worf: Fizz-1, TriD-5
    Data: Fizz-2, TriD-6
    Riker: Fizz-3, TriD-4

    This satisfies all the conditions. Picard is two behind Troi at Fizz. The person worst at Fizz (Fizz-1 - Worf) is better than Troi at TriD (Worf is 5, Troi is 3 at TriD). The person ranked 3 at TriD (Troi) is four positions higher than Data at Fizz (Data is Fizz-2, Troi is Fizz 6). Riker is two lower at TriD than the crew member ranked 2 at Fizz. (Fizz-2 is Data, Data is TriD-6, meaning Riker is TriD-4).

    Now to the heroes and fears. Clue 4 gives us a portal from the rankings to the heroes. Worf's hero is 3 times lower at TriD than the crew member who is best at Fizz. Troi is best at Fizz, Troi's TriD ranking is 3, so Worf's hero is TriD-1: Picard.

    Rule 10 tells us Riker is the hero of Worf's hero, so Picard's hero is Riker.

    Rule 5 tells us Picard's hero fears Geordi. So Riker fears Geordi, which also means Geordi is not Riker's hero.

    This leaves us with:

    Worf's Hero: Picard

    Picard's Hero: Riker

    Riker's Hero: Troi or Worf. It's not Picard, not Geordi, not Data (because of rule 7, Data is the hero of Riker's hero. Riker cannot be his own hero, so Data can't be his hero.)

    Data's Hero: Troi or Worf. It's not Riker, not Picard, not Geordi (rule 6).

    Geordi's Hero: Troi, Worf, or Data. It's not Riker, not Picard.

    Troi's Hero: Geordi. Because Geordi has been eliminated as a possible hero of all other people.

    Now, there are 3 people who don't have heroes yet: Geordi, Data, and Riker. Of these 3, Geordi is the only one who can have Data as a hero. So Geordi's hero must be Data. However, rule 7 states that Data is the hero of Riker's hero. Geordi cannot be Riker's hero because Riker fears Geordi.

    There is no way around this. My rankings abide by all the rules, and lead to Picard being Worf's hero. But if we follow the rules from that point, there is a direct contradiction and the puzzle is unsolvable.

    I've spent about 8 hours the past two days working on this, and finally searched for an answer online, which has led me to your blog. If you can, please tell me where I've gone wrong, if I have, because this has exhausted me.

    ReplyDelete
    Replies
    1. Without going through your work in detail, I think the fact that you find the hero/fear part to be unsolvable means that you must have gone wrong with the rankings part, even if your answer seems consistent with the statements dealing only with rankings. There are many different possible solutions to the rankings part, if you ignore the hero/fear part. But there is precisely one solution to the hero/fear part considered on its own. The only way to solve the puzzle is (I suspect) to begin with the hero/fear part, and then use the statement about Worf's hero to feed into the rankings part.

      When I first attacked the puzzle I made a mistake on the hero/fear part. Then, when I moved on to the rankings, I found that several solutions were possible. But when I went back and corrected my mistake, I found that precisely one solution was possible for the rankings.

      Hope that helps!

      Delete
  2. The mathematician in me finds it interesting that a wrong solution to heroes/fears leads to a rankings problem with many solutions, whereas a wrong solution to rankings leads to a heroes/fears problems with no solutions...

    ReplyDelete