Author |
Topic: Solving Who's Who Questions (Read 35316 times) |
|
James Fingas
Uberpuzzler
Gender: 
Posts: 949
|
 |
Solving Who's Who Questions
« on: Nov 8th, 2002, 12:12pm » |
 Quote  Modify
|
Solving those pesky figure-out-who's-who questions
Despite the fact that these question seem very difficult to solve, they are actually easier than they appear, especially if you have the right tools for the job. As an example for this method of solution, I'll use Eric Yeh's "Puzzle Forum" riddle, without considering the Uberpuzzler influence. If you haven't already done so, you'll want to read Eric's story, and here is the link:
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_har d;action=display;num=1031619416
Start by writing down all the possibilities. In this puzzle, we know exactly who all the actors are, so we just have the six permutations of these three people. I will call the uberpuzzler U, the newbie N, and the senior riddler S.
UNS
USN
SNU
SUN
NSU
NUS
This is the starting point for my method. From here, we decide to which person we'll addresss our first question. By symmetry, it doesn't matter initially, so we'll pick person #1. Now if we ask person #1 a question, we can get a correct or an incorrect answer if they are N or S (remember, we are ignoring Uberpuzzler influence). If person #1 is U, then we can only get a correct answer.
We are going to draw out both responses to the question (both "yes", and "no) below our initial six possibilities, in a tree-like form. The newbie will appear under both, because, no matter what the question, the newbie can answer either way. We can select where U will end up, and although S can answer either way, we can choose which answer will be false, and which will be true. I will denote the senior puzzler who has answered falsely as S'. Here is one way I can make the question turn out:
| \
Y N
| \
NUS NUS
NSU NSU
S'NU SNU
S'UN SUN
UNS
USN
I have "steered" the S' and the U together into the same column. Since these people are always perfectly reliable, then for four of the six possibilities, I can get a good answer from person #1. The N's propogate into both columns, because they can always answer either way.
For the next step, I break down each of these possibilities. I will consider the 'Y' column first. The best person to ask is, again, person #1. Here is how I will split the people up:
| \
Y N
| \
NUS NUS
NSU NSU
S'UN S'NU
USN UNS
Notice how I've made sure there is one person, for each response, that is definitely NOT the newbie. This ensures that i'm not wasting questions later on. I'll again consider the 'Y' column. I'm going to ask a question to person #2, splitting it up again:
| \
Y N
| \
NUS NSU
NS'U USN
S'UN
US'N
Notice how I've lumped the S' with the U again. Now in the 'Y' column, person #2 is perfectly reliable. Two more questions gives me 2 bits of information, so I can differentiate between exactly four possibilities. Excellent. In the 'N' column, I will also direct my questions to person #2. Here, I can still get a wrong answer, but if I ask the same question again, then I am sure to get the right answer the second time. Since I only need one bit of information to differentiate between two possibilities, then I've got this one in two questions as well.
I hope that after this brief introduction to the full-decision-tree method for deciding who's who, that you can finish off this example. Note that this example is the start of one optimal solution for the "Puzzle Forum" without Uberpuzzler influence. The solution is complete when every leaf on the tree has only a single possibility.
The main benefit to this method is that you don't have to think about the wording of the question until you are sure that your overall method is good. It removes that vague uncertainty that maybe you're not asking just the right question--you can tailor your question to do exactly what's best, and figure out how to word it later!
For instance, my first question could be "are you an Uberpuzzler?", because this fits all the appropriate responses. My second question could be "is person #3 a Newbie?", my third question could be (to person #2) "are you an Uberpuzzler?", etc.
PS. I know this will make my "Love Triangle" puzzle easier for you, but I'm sure you'll need it!
|
|
 IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
 |
Re: Solving Who's Who Questions
« Reply #1 on: Nov 8th, 2002, 7:26pm » |
Quote Modify
|
Great writeup, James. I'd settled on basically the same method after working on Eric's puzzles for a while, too. I used to repeatedly invent questions that I intuited would be useful and test them, but that was too inefficient for the really tough puzzles.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Solving Who's Who Questions
« Reply #2 on: Nov 11th, 2002, 7:11am » |
Quote Modify
|
Tim,
I agree--there really are a lot of questions out there, and it's difficult to know ahead of time if they'll be useful. I know that my first questions I came up with were sub-optimal. Unfortunately, some puzzles don't allow this linear sort of thinking (eg. Puzzle Forum with influence), but I think it can still be helpful in those circumstances.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Solving Who's Who Questions
« Reply #3 on: Nov 17th, 2002, 9:29pm » |
Quote Modify
|
Wow. Very nice! Exactly the kind of meta-level content I was hoping for in this section of the forum. If we have a few more of these, I wouldn't mind featuring articles like these on the main site in a new section. Most riddles might be difficult to breakdown like this (e.g. algorithm design) though. Over winter maybe I'll do one on NP Completeness proofs from the CS section -- unless someone beats me to it, which is fine with me. NPC problems usually come down to knowing about six key NPC problems real well.
|
| « Last Edit: Nov 18th, 2002, 8:51pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Solving Who's Who Questions
« Reply #4 on: Nov 21st, 2002, 12:00am » |
Quote Modify
|
In hindsight, I think this superficially helpful post was actually an elaborate red herring! I didn't find this method the least bit useful in working on Love Triangle, though I definitely used it intensively on Eric Yeh's puzzles. 
|
|
IP Logged |
http://tim-mann.org/
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Solving Who's Who Questions
« Reply #5 on: Nov 22nd, 2002, 11:18am » |
Quote Modify
|
Tim,
Do you think that I'd post this just so that I could laugh as you tried to apply this method to a question it could never solve? Surely not!
Actually, I did find this method useful for the Love Triangle, once I augmented it with a state diagram. I came to a slightly deeper realization about solving who's-who questions that I will now share (although I'm sure Tim already knows this):
Occasionally, you will find that you're not sure which way is the best to split up the possibilities in a question. You must look a step ahead and discover which possibilities can be separated from each other in a single question, and which cannot.
For instance, the following scenario (from the Puzzle Forum sans influence) is impossible to solve in one question:
SNU
S'UN
If you ask a question to either S or N in possibility SNU, then SNU will appear in both response columns. It is possible to differentiate between two different responses only if one of the people is always reliable. In fact, you can solve the above scenario in two questions, but you MUST ask person #1 both questions. Persons #2 and #3 cannot help you because they might be unreliable.
For example, the following scenario is solvable, because person 2 is known to be reliable:
SUN
NS'U
Futhermore, consider the following hypothetical scenario:
NUN
UNN
Let's say we ask person #1 a question. Since, in NUN, person #1 is unreliable, NUN will appear in both response columns. In possibility UNN, person #1 in UNN is perfectly reliable, so you can steer UNN into either response column. However, this doesn't help you, since in one of the two columns you'll end up with exactly the possibilities you started with.
This is why the Love Triangle puzzle as first stated is unsolvable. When you learn who one person is, you have a scenario like this:
ABC
ACB
There are only a few fundamentally different ways of asking a question, and in every single way, the subject will lie in one scenario, but tell the truth in the other scenario (actually, sometimes the subject lies in both scenarios, but this is even less helpful). Therefore, one of the two possibilities will always end up in both response columns, and the other possibility has to go somewhere, so for one response, you learn nothing.
Actually, it's only chance that you learn who one person is. The real problem, as was pointed out in the Love Triangle thread, is that when a question will be answered truthfully in one rotation, in the other rotation it will always be answered spitefully. It just so happens that whenever you pick two possibilities, one from each rotation, a single person is in the same place in those different possibilities.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Solving Who's Who Questions
« Reply #6 on: Nov 22nd, 2002, 3:54pm » |
Quote Modify
|
I really did think you might have posted it as a red herring! That would have been a clever bit of misdirection, and I would have thought of it as being in good fun, not meant (shall I say) spitefully. But I see now how using that method could still be helpful in showing the puzzle is unsolvable. I just happened to get to that without going into enough detail to need the method.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Solving Who's Who Questions
« Reply #7 on: Nov 25th, 2002, 9:50am » |
Quote Modify
|
Tim,
I guess I just got to the point of knowing one person very early on, and I figured out at that point (using my state diagram and exhaustion of possibilities) that the Love Triangle was impossible to figure out.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
CowsRUs
Full Member
Why is it that cats are better then cows? Why not?
Gender:
Posts: 175
|
|
Re: Solving Who's Who Questions
« Reply #8 on: Feb 11th, 2007, 2:35pm » |
Quote Modify
|
I don't get it
|
|
IP Logged |
"It is very good to have a brother who has a cow. It is also good to have a brother who has two cows. In fact, a brother with a cow is great, except when he has exactly 135 cows and is one of thecow himself."-Unknown
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Solving Who's Who Questions
« Reply #9 on: Feb 11th, 2007, 7:55pm » |
Quote Modify
|
Not much to go on. Could you be more specific about what you find confusing?
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
marlonmark
Newbie
Gender:
Posts: 43
|
|
Re: Solving Who's Who Questions
« Reply #12 on: Jan 6th, 2013, 10:51pm » |
Quote Modify
|
Still it looks very strange for me to find the solution. I guess will have to look for more examples.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
