Problem: A traveler comes to a fork in the road. One path leads to the land of L, where people always lie, the other path to the land of T, where people always tell the truth. At the fork is a man, but the traveler does not know if the man is from L or T. We can ask him only one question.
What question should the traveler ask to ensure he gets to T?
Solution: Let's draw a picture, as this often helps find the solution.
Pic 1 shows the problem, where we have encountered a man from L or T and we are trying to find the correct path to T.
If the man is from L, he will always lie. If he is from T, he will always tell the truth. We have to determine a question, which will allow us to know which way to go, irrespective of whether he is from L or T.
It's better not to just start randomly guessing (unless you immediately see the solution), so let's try to think structurally about what we are trying to get out of the question:
1. The question must allow us to choose the correct path
2. The answer must be definitive
3. The answer must not depend on whether the person is from L or T. It must be definitive irrespective of the person's home.
Most obvious questions fail this test, e.g.,:
- Which path takes me to T? -- fails because we do no know from the answer where to go
- Which path takes me to L? --If we could get this answer, we could do the opposite, but again, fails
--Are you from L or T?-- They both say T in this answer, and we don't know where to go?
Let's think about a two question combination that could work. This is in fact trivial.
ny question that uniquely determines where the person is from, e.g.,:
What is 2+2? to determine if the person is from L or T, then
Which path goes to T?
Unfortunately, we don't have two questions (and we can't put both in one question). One thought here is to try to ask a question that reveals both the person and answers something about the path, like: What path is the best path? But again, this doesn't work either.
At this point, let's look at the two question combination? Is there anything that we don't need in there? Well, one thing is that we actually figured out too much -- we don't actually need to know what city the man is from.
So, with this insight, we simply need to know the right path, and we have essentially a true and a false. We can use these to cancel each other out.
For example, we can ask the man, "What path would the other person say goes to T?" Hence, each will give the path to F." Then, we can take the opposite.
There is nothing terribly tricky about this problem. The important thing is to be structured, not just start guessing and to try to glean insights of what is needed and not needed. Some people find truth tables helpful in this problem, but I never have.
Also, there are other questions, but they typically involve negating either with someone from 'your town' or 'the other town', e.g., "What path leads to your town (negating with yourself)?"
/* Please let me know if you find bugs or alternate solutions. Thx, Noah */
Code WorkOut of the Day -- Daily exercises for programmers looking for jobs, or just to keep sharp with skills and have fun. I give talks, like this: https://youtu.be/NpvTE7GlXSM for people looking for jobs, or groups of programmers preparing for M&A tech HR due diligence. Follow us on twitter: @codewod
How to
When solving these problems, learning by doing is much better than learning by reading. I encourage to you read only as far in the solution as you need, then trying to solve the problem. If you get stuck, try reading a little further. And of course, let me know if you find a better solution!
No comments:
Post a Comment