Danny ChaiToday was one of those days that make me feel like I’m really going to miss Stanford. It was just a picture perfect day, and walking around campus was just a total joy. I’m serious, if you’re not enjoying the weather, and you can, there’s just something wrong. Play basketball, or swim, or jog, or do something, but you gotta get outdoors.
It makes me sad because I’m not gonna get a time like this again, when I’m free during the day to enjoy the weather. I’ll have to work and all that, be stuck in an office or something. It just made me a little sad. You know I’m enjoying the weather this quarter though. I’m taking frequent day trips to Vasona.
The other thing is I was sitting in CS 224M lecture. I know many of you won’t be able to relate, but I love learning. When I feel like I’m learning something really interesting, I just totally dig lecture, and get excited to be there. There’s no feeling like it. I felt this way with CS 224M, CS 227, and CS 228. It needs to be a little hard, so I struggle to understand a little. It’s a fun thing.
And this is coming to an end also. I don’t know, it’s just a little sad.
Anyway, this puzzle came up in CS 224M, and I thought I’d share it with you.
So there are 5 kids, and they’ve been playing in the mud. As a result, 3 of them have mud on their foreheads. But while they can see everyone else’s forehead, they can’t see their own, so they don’t know whether they’re dirty or not.
So their father calls them in and tells them, “at least one of you has a dirty forehead.” He then tells them if anyone knows whether they have dirt on their foreheads, to raise their hands. None of the children do. He then asks the exact same question again. Again, no children raise their hand. He then asks the exact same question again. This time, the 3 children with dirty foreheads raise their hands.
How can this be? Assume all the children are perfectly logical, and that they know that everyone else is logical.
Here’s another puzzle. So there are 10 prisoners. The executioner tells them that the next day, they will be lined up single file, so each prisoner can only see the prisoner in front of him. Each of them will be given a hat, red or black, such that you can’t see what’s on your head, and can only see the color of the hats of the people in front of you. So the last person in line can see the hats of everyone in front of him, and the person in the front can see no one’s.
Starting from the back, the executioner will ask each prisoner the color of his hat. If the prisoner gets the color correct, he will live; otherwise he will die.
The question is, how many prisoner can be saved? Besides using just random luck. How many prisoners can you expect to save? And how do you do it? The correct answer is obviously more than 5.
Another question. You have 12 balls. They all look identical. Except one is heavier or lighter than the others. The thing is, you don’t know which ball is heavier or lighter, and you don’t know whether it’s heavier or lighter. You also have a balance scale. Using just 3 weighs of the balance, how can you figure out which ball is odd, and whether it is heavier or lighter?
Another question. You are a prisoner. You must choose between 2 doors – one door leads to death, the other to freedom. There are also 2 guards, one by each door. It is known that one of them always tells the truth, and that one of them always lies. Before you choose, you are allowed to ask a single question to only one of the guards. What question do you ask to figure out which door leads to freedom?
Finally, assume that instead of 2 guards, there are 3 guards guarding the doors. It is known that one guard always lies, that one always tells the truth, and that one sometimes lies and sometimes tells the truth. You are allowed to ask 2 questions, and each question must be addressed to only 1 of the guards. What questions do you ask to figure out which door leads to freedom?