The Island of Democrats and Republicans

On February 10^th, the world lost Raymond Smullyan: logician, puzzlemaster, and blue-ribbon Gandalf lookalike.

Even if you don’t know his name, you’ve probably wrestled with his logic puzzles. They share a whimsical sense of rigor: “You come to an island where there are two types of people: knights, who always tell the truth, and knaves, who always lie…”

They’re silly and frustrating and fun; everything mathematics should be. I love this origin story for how Smullyan first got into such puzzles:

On 1 April 1925, I was sick in bed… In the morning my brother Emile (ten years my senior) came into my bedroom and said: “Well, Raymond, today is April Fool’s Day, and I will fool you as you have never been fooled before!” I waited all day for him to fool me, but he didn’t.

Or did he?

Young Ray had spent all day expecting to be fooled. But the fooling had never come. Didn’t this constitute the greatest fooling of all?

I recall lying in bed long after the lights were turned out wondering whether or not I had really been fooled.

In Smullyan’s honor, I wanted to offer up my own amateur variant on his knights-and-knaves puzzles.

I call it: the island of Democrats and Republicans.

Now, Republicans and Democrats look identical to an outsider like you. But they always recognize one another immediately. And because of their mutual antipathy, they follow this strange custom:

So, here comes your puzzle. Ten of them, really.

Part 1: Wandering around the island, you overhear some conversations between islanders. From each statement, you try to figure out the political parties of the speaker and the listener. What can you conclude?

Solutions to Part 1:

1. You can conclude nothing—they always say this to each other!
   If they ARE from the same party, then it’s true, so they’ll say it.
   And if they’re NOT from the same party, then they’ll lie and say they are!

2. You’re hallucinating—this never happens!
   As discussed in #1, two people speaking to each other always claim to be from the same party, never opposite parties.

3. The speaker is a Republican.
   The speaker must either be telling the truth to a fellow Republican, or lying to an opposing Democrat.

4. The listener is a Republican.
   The speaker is either telling the truth to a fellow Republican, or lying to an opposing Republican.
5. They’re both Democrats.
   If both were Republicans, they wouldn’t say this, because it’s false.
   And if one were from each party, they wouldn’t say this, because it’s true!

6. They’re both Republicans, following the same essential logic as #5.

Part 2: Next, you witness some strange conversations between multiple people. What can you conclude from each?

Solutions to Part 2:

7. A must be a Democrat (see problem #4).
   If B is also a Democrat, then C must be a Democrat, too.
   But then, B’s statement to C is a lie, which isn’t possible.
   So B is a Republican.
   B tells the truth to C, so C is also a Republican.
   Thus, A is a Democrat, while B and C are Republicans.

8. C’s statement must be true, because if it were a lie, then they’d all be Republicans, and so there’d be no reason to lie.
   Thus, C and A are from the same party.
   If C and A are Democrats, then B is telling the truth to C, which means they’re all Democrats—but that’s impossible.
   So A and C are Republicans, and B must be a Democrat.

9. Based on Z’s final statement, A must be a Democrat (see problem #4).Now consider Y’s statement. If Y is telling the truth, then Y is a Republican, and so Z must be a fellow Republican. If Y is lying, then Y is a Democrat, so Z must be a Republican. Either way, Z is a Republican.Thus, A is lying to B.
   Thus, B is a Republican.
   B tells the truth to C, so C is a Republican.
   C tells the truth to D, so D is a Republican.
   And so on!Thus, A is a Democrat, and everyone else is a Republican.

10. Odds claim to share a party with N, and evens do not.
    As discussed in Questions 1-2, anyone speaking to N must claim to share a party with N. Thus, N – 1 must be odd, which means N is even.Suppose that 1’s statement is a lie.
    This means 1 and 2 are from different parties.
    This makes N’s statement to 1 true; there is a Democrat among them.
    Thus, N and 1 must be from the same party.
    But 1 makes that claim when speaking to 2, who is from the opposite party—so this scenario is impossible.Hence, 1 and 2 are from the same party.
    So is N, because 1 is telling the truth to 2.
    Thus, because of N’s statement to 1, all three are Democrats.This means 2 is lying to 3, so 3 is a Republican.
    Similarly, 3 is lying to 4, so 4 is a Democrat.
    Moreover, 4 is lying to 5, so 5 is a Republican.
    And so on…

    Thus, 1 and all evens (including N) are Democrats.
    All odds except 1 are Republicans.

Thanks to my father for his help editing the solutions and trimming Problem 8!