wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> general problem-solving / chatting / whatever >> Solving Who's Who Questions
        
(Message started by: James Fingas on Nov 8^th, 2002, 12:12pm)

Title: Solving Who's Who Questions
Post by James Fingas on Nov 8^th, 2002, 12:12pm

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_hard;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!

Title: Re: Solving Who's Who Questions
Post by TimMann on Nov 8^th, 2002, 7:26pm

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.

Title: Re: Solving Who's Who Questions
Post by James Fingas on Nov 11^th, 2002, 7:11am

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.

Title: Re: Solving Who's Who Questions
Post by william wu on Nov 17^th, 2002, 9:29pm

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.

Title: Re: Solving Who's Who Questions
Post by TimMann on Nov 21^st, 2002, 12:00am

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. ;)

Title: Re: Solving Who's Who Questions
Post by James Fingas on Nov 22^nd, 2002, 11:18am

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.

Title: Re: Solving Who's Who Questions
Post by TimMann on Nov 22^nd, 2002, 3:54pm

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.

Title: Re: Solving Who's Who Questions
Post by James Fingas on Nov 25^th, 2002, 9:50am

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.

Title: Re: Solving Who's Who Questions
Post by CowsRUs on Feb 11^th, 2007, 2:35pm

I don't get it

Title: Re: Solving Who's Who Questions
Post by Icarus on Feb 11^th, 2007, 7:55pm

Not much to go on. Could you be more specific about what you find confusing?

Title: Re: Solving Who's Who Questions
Post by ChrisPBacon on Jun 21^st, 2008, 8:13am

So many words!

30th post! :P

Title: Re: Solving Who's Who Questions
Post by atyq on Aug 3^rd, 2012, 12:12am

Thanks for solving those pesky figure-out-who's-who questions.
I wanted to find the answer, it was very difficult to find it.

Title: Re: Solving Who's Who Questions
Post by marlonmark on Jan 6^th, 2013, 10:51pm

Still it looks very strange for me to find the solution. I guess will have to look for more examples.