Logic Puzzle: The Joy of Recursion | Hacker News Reader

Logic Puzzle: The Joy of Recursion

quantamagazine.org

65 pointsdigital5513 comments

I was confronted with recursion early on, but didn't really see the point outside of tree/graph traversals. It just didn't seem worth the effort given lousy performance and constant risk of stack overflow.

Then I started writing Lisp, and the &rest is history.

The cool thing about optimized tail recursion is that any loop you can dream of [0] is just a macro away. It also helps with keeping the core of the language clean, as fewer primitives are needed.

https://github.com/codr7/g-fu#macros

The legislators puzzle is well known and is actually an induction puzzle rather than recursion.

A better more easily understood version of the same puzzle is here : https://en.wikipedia.org/wiki/Induction_puzzles

Joesphine's Puzzle.

The joy of recursion or the joy of induction? :)

The first one reminds me of the buffalo puzzle:

Buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo.

Add capitalization (and, optionally, two linking words) so that the above makes sense.

>Puzzle 2: The Lying Legislators

I believe this is the same question as the Blue Eyes one from XKCD [1], though with a more coherent premise.

1. https://xkcd.com/blue_eyes.html

The Blue Eyes puzzle was a tough one to wrap my head around until I shrank the problem much smaller.

Imagine there are only two people on the island, A and B. A has blue eyes, B has brown eyes. When the guru makes his announcement, A sees that B has brown eyes, and deduces that he himself has blue, and gets on the boat at midnight.

Now, imagine BOTH A and B had blue eyes. On day 1, neither of them get on because they don't know their own eye color. The second day, though, A thinks "If I had brown eyes, then B would seen them and figured out that he's the only one with blue eyes on day 1 and gotten on the boat, but he didn't. That means I have blue eyes as well." B thinks the same thing, and gets on the boat.

Try it with three people, A, B, and C, with A being the only blue eyed person. On day 1, A sees no blue eyes and figures out he's the only one with blue eyes and gets on the boat. Simple.

But what if A and B are blue, and C is brown? A and B both see 1 person with blue eyes, C sees 2 people with blue eyes. It's important to note that A and B both believe there's either 1 or 2 people with blue eyes, and C believes there's either 2 or 3 people with blue eyes. On day 1, A and B know there could be 2 people with blue eyes including themselves and don't get on the boat. C sees 2 people, and knows he could be a third, and doesn't get on the boat. On day 2, A notices B didn't get on the boat and knows that B also knows that C has brown eyes. The only logical conclusion is that B didn't get on the boat because he saw A's blue eyes. And so A gets on the boat because he knows he has blue eyes. Likewise, B sees that A didn't get on the boat, and knows that both of them know that C has brown eyes, and also concludes he has blue eyes. C knows how A and B concluded they had blue eyes (Remember that they're all perfect logicians!), and concludes he has brown eyes.

What if all three have blue eyes? For days 1 and 2, they all have the same logic as C did in the previous paragraph. They all know there's at least 2 people with blue eyes, and possibly 3.

Let's jump ahead a bit. 6 people, A through F, and A, B, and C have blue eyes. On day 3, A looks around and notices that B and C didn't leave. A knows that B and C know that D, E, and F all have brown eyes. But because A knows that if there were only two people with blue eyes (B and C), they would have figured it out on day 2. That means there MUST be three people with blue eyes, and since he knows B and C have blue and D, E, and F have brown, he's the only possibility for having blue eyes. B and C come to the same conclusions themselves, announce their blue eyes, and get on the boat at midnight.

No matter how many people there are and how many of them have blue eyes, if the actual number of people with blue eyes is N, then all the blue-eyed people know there's either N (They see all the people with blue eyes and and they themselves have blue eyes) or N-1 (They see all the blue eyes and they DON'T have blue eyes) blue eyed people, where N is the actual number of blue eyed people. The brown eyed people all know there's either N or N+1. On day N, all the people with blue eyes will have figured out that they have blue eyes and will get on the boat because if the number of blue eyes was N-1, then they would have gotten on the boat the previous night. Meanwhile, all the people with brown eyes will still be waiting because they don't know if the number is N or N+1.

Why is the guru's announcement required in the case of 100 blue - 100 brown? What additional information was provided to the islanders?

That's the hard question to answer. The best I can explain is that the guru's announcement is necessary to create the base case for the induction.

Imagine the 4-person scenario with 2 blues and 2 browns. Is it common knowledge that blue-eyed people exist? You might think, "Of course, because each blue-eyed person can see 1 other blue eyed person!" But keep in mind that nobody knows their own eye color. Blue-eyed person A doesn't know their own eye color, so he doesn't know that blue-eyed person B can see A's blue eyes. If blue-eyed A believes he has brown eyes, then he knows that blue-eyed B won't see any blue eyes! The fact that blue-eyed people exist is not common knowledge!

Add third blue-eyed person C. You'd think the above paragraph falls apart, but it doesn't. C knows that A sees B's blue eyes, sure. But C doesn't know that B knows that A knows that C has blue eyes, because C doesn't know his eye color! The idea that there are at least two people with blue eyes is not actually common knowledge, because again, nobody knows their own eye color. In addition, the sentence "A knows that B knows that C knows there's at least 1 person with blue eyes" isn't actually true, though it may seem that way at first glance. For it to be true, A would have to assume that he has blue eyes, because he's the one doing the presumption. B knows that C knows there's at least 1 person with blue eyes because B knows that C sees A. But A doesn't know the previous statement because he doesn't see A, because it's himself!

It's certainly hard to wrap your head around. There's other explanations at http://forums.xkcd.com/viewtopic.php?t=80149

Thanks for taking the time to write this up.

Thank you, I can go to sleep tonight now.

> though with a more coherent premise.

I much prefer the XKCD version, which expresses the core idea more succinctly. The quanta version is like reading verbose code that misses the essence of a problem.

The premise is incoherent. As noted, they all see legislators with long noses and know how many they have seen, so there is nothing special about the day the Truon came visiting.

Second, they all know they are liars, nose or no nose, so they should have resigned immediately.

The only way the puzzle makes any sense is (1) the liars have a blind spot about their lies, and nobody ever gets on their case about the lies (nose or no nose), and (2) the legislature hasn't been meeting very long. The Truon just happened to show up before they would all have resigned anyway. So, you can't tell how many there were, because you don't know when they first met.

The blue-eyed islanders have the second problem.

I think 1 is assumed, that they're oblivious about their lies. But then why do the Truons or the Guru in the Blue Eyes puzzle matter?

Reply on news.ycombinator.com