wu :: forums « wu :: forums - Solving Who's Who Questions » Welcome, Guest. Please Login or Register. Apr 1st, 2023, 7:41am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    general problem-solving / chatting / whatever (Moderators: Eigenray, SMQ, william wu, Icarus, ThudnBlunder, Grimbal, towr)    Solving Who's Who Questions « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Solving Who's Who Questions  (Read 35205 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

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

william wu

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

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

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
ChrisPBacon
Newbie

Roflcopters and lawlerskaters!

Gender:
Posts: 35
 Re: Solving Who's Who Questions   « Reply #10 on: Jun 21st, 2008, 8:13am » Quote Modify

So many words!So many words!So many words!So many words!

30th post!
 IP Logged
Technologeek
Junior Member

Any problem? Contact me by MP

Gender:
Posts: 52
 Re: Solving Who's Who Questions   « Reply #11 on: Aug 3rd, 2012, 12:12am » Quote Modify

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

Against Wikipedia totalitarism - Proofs Wiki: The Mean value theorem proof and
Fundamental theorem of calculus
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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ => general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »