Author |
Topic: Love Triangle (Read 1688 times) |
|
James Fingas
Uberpuzzler
Gender: 
Posts: 949
|
 |
Love Triangle
« on: Nov 7th, 2002, 11:27am » |
 Quote  Modify
|
The Love Triangle
Here is the story of three unhappy people: Angelica, Bernardo, and Cameron. Angelica and Cameron have been friends since childhood. Cameron is hopelessly in love with Angelica, but Angelica has always thought of Cameron as "just a friend".
During high school, a new boy, Bernardo, moves into the area. Bernardo immediately catches the attention of Angelica, who falls head-over-heels for him. However, Bernardo is not interested in women--he is strongly attracted to Cameron. Cameron, of course, is jealous of Bernardo, because he has stolen Angelica's love away. Angelica is angry at Cameron, because she feels that Bernardo's lack of attention to her is Cameron's fault. Bernardo is jealous of Angelica, who recieves all of Cameron's attention. What are these three to do? (Please, this is a rhetorical question--there is no need to answer it)
One day, you meet them, all together in a chat room. They are all using nicknames: Uberkewl, Vaxxipaxx, and Willywutang (in no particular order). Because they are so jealous and screwed-up, each of them will only answer a question truthfully only if:
1) one of your last two questions was to their sweetheart, and
2) your last question wasn't to the person with whom they are upset.
Otherwise, they will answer spitefully--giving you the answer that will confuse you the most.
Your task is to figure out who is who. Is it possible? If so, how many question might you have to ask?
|
|
 IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
 |
Re: Love Triangle
« Reply #1 on: Nov 7th, 2002, 2:13pm » |
Quote Modify
|
Could we clarify what it means to say "the answer which will confuse you the most"? It seems to me that that would depend on the strategy the questioner is using. For example, I might ask each "question" as 27 separate sets of three questions, covering all possible strings of three people, and then comparing the answers a person gives in the different circumstances (yes, I realize that there's room for optimization, here). If that's my strategy, then the most confusing thing they could do would be to always answer correctly (because then, there would be no differences in their answers, in different circumstances). But if they're always answering correctly, then I can just use a different strategy, and ask questions directly.
Perhaps if we say that they just answer randomly if we don't ask correctly, so we can't assume anything about their "strategies"?
A couple of other clarifications: Are we restricted to yes-no questions? And what do they do for the first two questions (confuse, I presume)?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Love Triangle
« Reply #2 on: Nov 7th, 2002, 11:54pm » |
Quote Modify
|
well.. I think ..
There's really just two directions in which to ask question, UVW(repeat) or UWV(repeat). In one direction you'll allways ask the one the next one hates a question last, the other way round you allways ask the one they love a question last..
If you get confuced change the direction.. 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Love Triangle
« Reply #3 on: Nov 8th, 2002, 10:02am » |
Quote Modify
|
Chronos,
What I'm saying is that when they answer spitefully, sometimes they will answer correctly, and sometimes they will answer incorrectly. I am telling you there is no way to predict the truthfulness of a spiteful answer. Analyze the worst-case scenario.
The questions are intended to be yes/no, but if you have any interesting proposals for other questions, feel free to suggest them. Keep in mind that you don't know much about these people, so it could be very hard to judge the veracity of a non-yes-or-no question.
They are suspicious at first, and will answer your first question spitefully. Second and subsequent questions follow the stated rules.
|
| « Last Edit: Nov 8th, 2002, 12:59pm by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: Love Triangle
« Reply #4 on: Nov 8th, 2002, 12:33pm » |
Quote Modify
|
Well, let's at least start on the analysis. I can think of five distinct questions (along with boolean combinations of the same) which we can ask U:
Are you A?
Are you B?
Are you C?
Do you like V?
Is the sky blue?
Of course, if we're talking to V, we ask if he/she likes W, and we ask W about U. All other questions about who of {U, V, W} likes each other are equivalent to this question.
Further, questions of the fifth type aren't going to help us: Whenever we ask a question to which we already know the answer, the answer will always be correct, regardless of how we ask. So that leaves four questions.
Further, as soon as we figure out the cycle of UVW, we've got it made.
I still think that they can always confuse us, but I'm not certain of exactly how.
|
|
IP Logged |
|
|
|
Garzahd
Junior Member
Gender:
Posts: 130
|
|
Re: Love Triangle
« Reply #5 on: Nov 8th, 2002, 2:14pm » |
Quote Modify
|
I can identify one of the three people in 11 questions. I'm still not sure if it's possible to get all three, however...
I'll wait on posting my semi-solution till I can either get the other two or can prove I can't. (or till someone else does)
|
|
IP Logged |
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: Love Triangle
« Reply #6 on: Nov 9th, 2002, 1:23pm » |
Quote Modify
|
Garzahd, how is it that you can get one, but not all three? Can't you apply the same method again, to get the second person (from whom the third follows by process of elimination)? Does your question rely on some particular interpretation of how the first two questions are answered?
And can we assume that the person who goes by Willywutang is one of the males?
|
|
IP Logged |
|
|
|
Garzahd
Junior Member
Gender:
Posts: 130
|
|
Re: Love Triangle
« Reply #7 on: Nov 11th, 2002, 10:01am » |
Quote Modify
|
Here's what I have so far. It's inefficient, but it seems the best we've got at this point.
1) U: throwaway
2) V: throwaway
3) W: Are you A?
4) U: Are you A?
5) V: Are you A?
If not exactly one "yes" from 3-5, we're going the wrong direction. Continue with
6a) U: throwaway
7a) W: Are you A?
8a) V: Are you A? (by now, you know truthfully who is A)
9a) U: Are you B?
10a) W: Are you B? (done)
If exactly one yes from 3-5, then
6b) W: Are you B?
Now you have an ordering of A, B, C, but you're uncertain if it's correct. Now reverse:
7b) V: throwaway
8b) U: Are you A?
9b) W: Are you A?
10b) V: Are you A? (if not exactly one "yes" in 8-10, your original ordering was correct)
11b) U: Are you B?
Now you have two orderings, one of which must be right. If they coincide, you're done. If they don't coincide in any of the three seats, such as BCA/CAB, they must be the same rotation. You know A loves B loves C, so choose the ordering that corresponded to the rotation where you went in decreasing alphabetical order.
Otherwise, they must correspond in exactly one seat. So you know one person for sure. But they give different answers in each rotation, and I can't figure out a way to identify which is which.
(Given that there are six possible orderings, the 4 questions to identify which ordering they think they are could be reduced to 3, but the current one makes more sense for exploring the problem. To me, at least.)
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Love Triangle
« Reply #8 on: Nov 12th, 2002, 9:47am » |
Quote Modify
|
To clarify things, your very first question must be a throwaway, but the second question does not have to be (ie. Angelica will answer question #2 correctly if question #1 was to Bernardo).
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: Love Triangle
« Reply #9 on: Nov 13th, 2002, 1:12pm » |
Quote Modify
|
Quote:| To clarify things, your very first question must be a throwaway, but the second question does not have to be (ie. Angelica will answer question #2 correctly if question #1 was to Bernardo). |
|
If there is a solution, then this will let us trim it down a bit, but it won't get us a solution if there wasn't one before. We can always just ask the first two questions of the same person, and it'll be equivalent to just asking the first question of that person.
But I think I have a proof that we can't find a solution.
Suppose, without loss of generality, that the correct mapping is A -> U, B -> V, C -> W. Now suppose that, by conspiracy or coincidence, all three of the lovers have agreed that, whenever you ask questions in a way which you know is wrong (i.e., ask the same person three times in a row), they'll answer randomly. And if you ask in a way which is wrong, but you don't know that it's wrong, they'll answer as though the correct mapping were A -> U, B -> W, C -> V. Now, whenever you make an assumption about the correct order, all answers will be consistent with that order, and you won't be able to confirm nor deny that it's correct. So you can't figure out the right order.[edited to fix color]
|
| « Last Edit: Nov 13th, 2002, 1:16pm by Chronos » |
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Love Triangle
« Reply #10 on: Nov 13th, 2002, 1:44pm » |
Quote Modify
|
Chronos,
Seems like a nice proof, but maybe a touch hand-wavy. Do you have to assume which arrangement is correct before you can ask a question?
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Love Triangle
« Reply #11 on: Nov 15th, 2002, 10:57am » |
Quote Modify
|
Chronos's proof looks fine to me, although you could quibble a bit with the wording. I would say something like "try to draw a conclusion" in place of "make an assumption". I came up with the same idea last night and was just reading the thread this morning to see if anyone else had solved it.
Here's the way I'd have written it up. This is more verbose and thus perhaps not as good, but it's more detailed.
Suppose you're about to ask a question. Call the person you're about to query Q, call Q's sweetheart S, and call Q's enemy E. There are the following possibilities for the previous two people you've queried: QQ, QS, QE, SQ, SS, SE, EQ, ES, EE, --, -Q, -S, -E, where "-" means you hadn't asked a question yet. In the cases QS, SQ, SS, ES, and -S, Q is constrained to answer truthfully; in the others, Q can choose either answer. You don't know which is which between E and S.
Now suppose that A, B, and C conspire to confuse you as follows: in cases QQ, --, and -Q they answer randomly. In cases QE, EQ, EE, SE, and -E (i.e., the ones that correspond to cases where they must be truthful, except with E and S swapped), they all give answers that are consistent with a fictional world they have agreed upon, in which the identities of some pair of U, V, W are swapped from what they are in reality. Swapping one pair in this way also swaps everyone's sweetheart and enemy, which is what allows the fictional world to be consistent.
So no matter what questions you ask, there is no way for you to distinguish the real world from the fictional one. You can collect two sets of answers, each of which will be self-consistent, but you have no way to tell which set is which.
Notice that this conspiracy works only if two people swap identities: If everyone changes to someone else's identity, it's a cyclic permutation, and everyone retains the same S and E as before, so they would have to tell the truth in the same cases, not in the ones with S and E swapped. This isn't a complete proof that you can always find one person's identity, but it helps in understanding why you can. If Garzahd's answer is right (I didn't check it), he's already proved that constructively.
|
| « Last Edit: Nov 15th, 2002, 10:59am by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Love Triangle
« Reply #12 on: Nov 15th, 2002, 1:47pm » |
Quote Modify
|
That's a little more convincing, Tim. You are correct in that you can't find out the identities of U,V, and W, although it is interesting that you can always determine one person's identity. It seems like in this question, the more you know, the less you are able to find out!
Now let's say that you have an informant who has collected information for you, and can tell you any one of the following:
i) The person that U loves, before your questioning session
ii) The person that U loves, after your questioning session
iii) Who U is, before your questioning session
iv) Who U is, after your questioning session
Which of these pieces of information are useful? How many questions will it take in an optimal solution, with worst-case answers, given each of these pieces of information?
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Love Triangle
« Reply #13 on: Nov 15th, 2002, 3:09pm » |
Quote Modify
|
Quick partial response: (i) or (ii) is sufficient to find out who is who. With (iii) or (iv), V and W might be the ones who impersonate each other in the fictional world, so knowing who U is doesn't help -- we could find that out for ourselves. So (iii) or (iv) are not sufficient in general, only if we luck out.
Naively, we should be able to do with fewer questions given (i) than given (ii). I'll think of a questioning protocol later.
p.s. In (i) and (ii), I'm assuming you mean that the information given me is "U loves V" or "U loves W", not "U loves A" or "U loves B" or "U loves C".
|
| « Last Edit: Nov 15th, 2002, 3:14pm by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: Love Triangle
« Reply #14 on: Nov 15th, 2002, 4:26pm » |
Quote Modify
|
Given information (i), you need three questions. Say that you learn that U loves W. Then we also have that W loves V, and V loves U. So if you ask questions in the order UVWUVW... (or any cyclic permutation), you'll get all true answers (except for the throwaway first question). Once you know that U loves W, there are only three possibilities to distinguish, and it's just counting bits: Two reliable boolean questions are necessary and sufficient to distinguish three possibilities.
Given information (ii), five questions will suffice, asked to U, V, W, V, U, in that order. In either case, the first question will be a throwaway. If you learn that U loves W, then you can trust questions 2 and 3, and ignore 4 and 5. If you learn that U loves V, then you can trust questions 4 and 5, and ignore 2 and 3. Either way, you've got your two bits. I think that this is optimal, but I'm not certain.
|
|
IP Logged |
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Love Triangle
« Reply #15 on: Nov 15th, 2002, 7:11pm » |
Quote Modify
|
Chronos's answer sounds right to me. (I came up with the same thing since my last post.) It must be optimal because the first question has to be a throwaway, no question can have a trustworthy answer under both cyclic orderings, and you need two questions to have enough information to finish the problem. So you need at least 3 questions for (i) and 5 questions for (ii).
The alternative interpretations of (i) and (ii) may also be interesting: what if you're told something of the form "U loves A" rather than "U loves V"? This gives you enough info to solve the problem, but I'm not quite certain of the minimum number of questions. 5 certainly suffice, but can you do with fewer if you know the information in advance? I don't think so...
|
|
IP Logged |
http://tim-mann.org/
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Love Triangle
« Reply #16 on: Nov 15th, 2002, 9:46pm » |
Quote Modify
|
on Nov 15th, 2002, 7:11pm, TimMann wrote:| The alternative interpretations of (i) and (ii) may also be interesting: what if you're told something of the form "U loves A" rather than "U loves V"? |
|
Oops, I goofed on this. The puzzle is unsolvable under this interpretation. "U loves A" is exactly equivalent to "U is C", which we know is unsolvable because it may be V and W who switch identities in the fictional world.
|
| « Last Edit: Nov 15th, 2002, 9:46pm by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Love Triangle
« Reply #17 on: Nov 18th, 2002, 9:03am » |
Quote Modify
|
For item i), I did mean information of the sort "U loves V", as Tim is correct--"U loves A" is not always useful.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: Love Triangle
« Reply #18 on: Nov 20th, 2002, 3:45pm » |
Quote Modify
|
I just thought of something else, which makes my solution a bit more elegant: Not only can you do it in three or five questions, you can use the same question for each one. For instance, "Are you Angelica?"
|
|
IP Logged |
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: Love Triangle
« Reply #19 on: Nov 26th, 2002, 10:52am » |
Quote Modify
|
Hey guys,
Sorry to enter the conversation late; I just saw this problem.
First: James, cool problem! Very well-written. 
Here's the prooof I came up with, which I think is rather simple (I haven't looked ubercarefully at the other solutions, but they looked a little more complicated...):
Restrict to the case where you know it is either ABC or ACB. It is sufficient to show that for any sequence of questions you ask, you could get the same answers in either scenario. But that reduces to showing that for any three positions asked, (e.g. "first person, third person, first person"), the third person can answer the same thing in either scenario (from there the previous statement rolls). But this in turn is just to prove that the third person can always lie in at least one of the two scenarios.
The last statement is itself very easy to see -- it can be seen either empirically by looking at each of the 27 combinations (reducible by various symmetries), or theoretically, by the argument "WLOG ABC tells the truth, but if the last person is A then etc. etc. (there are actually only two cases, A or B/C).
Let me know if any of the "extra" problems are unsolved -- I haven't had a chance to read them carefully. When I get some time, I will perhaps post some more of my problems...
Best,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Love Triangle
« Reply #20 on: Nov 28th, 2002, 9:44am » |
Quote Modify
|
You guys made my Love Triangle Puzzle seem too easy, so I challenge you to solve ... the Love Square! I just posted it today. It's like the Love Triangle except:
1) I increased the sum of the interior angles by pi.
2) It's solvable. Honest! I'm from the City of Safety--would I ever lie to you?
3) There's more possibilities (that always seems to happen when you add more people)
4) The plot is exactly the same except for the stuff I changed. Well, maybe that's not the best way of putting it ...
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_har d;action=display;num=1038503997
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print