wu :: forums - Print Page


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

        riddles >> hard >> The Love Square
        
(Message started by: James Fingas on Nov 28^th, 2002, 9:19am)

Title: The Love Square
Post by James Fingas on Nov 28^th, 2002, 9:19am

The Love Square Sorry guys, but the love triangle was just too easy for you!

In the Hemlock Grove retirement villa, four seniors are discovering the joys and sorrows of a "love square". Amelia, Bertrand, Claire, and Donald have gotten themselves mixed up in a little more than they can handle.

Amelia has fallen for Bertrand, with his youthfully craggy face and his deep gravely voice. Bertrand does not realize this, and secretly admires Claire, with her youthful temperament and derring-do. Claire is oblivious to Bertrand's feelings, and is instead obsessed with Donald and his mysterious past. Donald doesn't know that Claire is interested in him, but he has the hots for Amelia.

Of course, Bertrand realizes that Claire likes Donald, and has secretly vowed to get Donald on the bad side of the cleaning staff. Donald shares Bertrand's emnity, since his beloved Amelia is bewitched by the old git. He has been trying to get a bird to build its nest over top of Bertrand's patio door for nearly a year now.

Amelia recognizes the glint in Bertrand's eye when he looks at Claire, and she is determined to sabotage Claire's next candlelight supper by replacing her baking powder with powdered salt. Claire is likewise jealous of Amelia, that slut, and she plans to run her over on the sidewalk with her electric three-wheeled buggy.

One day, you meet all four of these unhappy individuals in a chat room, going under the nicknames UsUxOrZ, VampireBob, WussMania, and Xanadu. Because they are all slightly crazy (they are in love after all), each person will only answer a question correctly if:

1) one of your last two questions was asked of their sweetheart, and
2) your last question was not to their enemy.

Otherwise, they will tell you whatever they feel like telling you. Is there any way that you can deduce the identities of these four individuals? How many questions must you ask to determine who is who?

Title: Re: The Love Square
Post by Eric Yeh on Nov 28^th, 2002, 10:28am

Yes, at first glance, I would certainly have to agree that this one is solveable. For example, you can just do the uber-dumb:

Ask B from each ABB who they are, and the result drops out. This takes a whopping 36 q's, which can be simply reduced to 24 by overlapping, which is certain to still be a dumb methodology.

Well, that's dumb but it works, and all I have time for this fine Thanksgiving afternoon (where I will soon need to run off to deliver some wine to my local pot luck :9 ). If I have a chance, I will try to find a real soln sometime after the holiday.

Happy Thanksgiving everyone!

Best,
Eric

Title: Re: The Love Square
Post by James Fingas on Nov 28^th, 2002, 11:09am

Eric,

I don't think that will work (if I understand your method). As I see it, you propose to ask three questions to every combination of two different people (there are 12 such combinations), in order UVV. You will only record the answer to the second question to V.

If the last two questions were to U and V, V will only answer the next question correctly if V loves U. Here is a set of possible answers that are consistent with two different orderings:

VUU: "A"
WUU: "A"
XUU: "A"
UVV: "B"
WVV: "B"
XVV: "B"
UWW: "D"
VWW: "A"
XWW: "C"
UXX: "D"
VXX: "B"
WXX: "C"

Happy Thanksgiving, although here in Canada we celebrate Thanksgiving in mid-October.

Title: Re: The Love Square
Post by Eric Yeh on Nov 28^th, 2002, 11:35am

Ye you're right, sorry; guess that was even more uber-dumb than I thought!! ;) Let me think about it more when I have a chance.

Best
Eric

Title: Re: The Love Square
Post by Eric Yeh on Nov 28^th, 2002, 12:21pm

Ok, here's a better pf of existence.

It is sufficient to show that you can differentiate between any two permutations sigma1 sigma2. I will show you can do so with three qs by forcing a correct answer on the third q, which clearly can be set appropriately to reveal the truth.

WLOG, sigma1 = e (the identity), and rename sigma2 s for short. First, suppose s(i+1)=s(i)+1 for any i \in {0,1,2,3}. Then let [position] x = s(i)+1 and y = s(i); asking xxy will force a correct third answer in both situtations (e and s).

The only other cases must be a rotation of the following: {0123} -> {0321} (this can be seen by fixing 0 and seeing subsequently where 1, 2, and 3 can go). Note that the only other distinct rotation is {1032} which is identical in structure, so there is only one distinct case. In either case, asking positions 130 guarantees a truthful response from postition 0. QED.

Now, how many questions does this add up to? Again without thinking too hard as yet, one simple thing is to ask each xxy for a fixed y, giving three possible permutations. Then use three questions as per the lemma above to eliminate two possibilities. The total cost is something like (using xxyyxxyy for each x as a slight optimization) 8+8+8+3+3 = 30 questions, without trying to think about savings on overlaps as yet. (BTW, I meant 25 instead of 30 above, since the first q would not be overlappable. This is irrelevant here, but I can't live w having a remaining error out there ;) ;) )

This time I'm less optimistic about optimizations. How much more time is it worth putting into this, James? Do you have a pf of optimality?

Best,
Eric

Title: Re: The Love Square
Post by Eric Yeh on Nov 28^th, 2002, 12:37pm

Woops, obviously still not thinking hard. Takes 5 qs to identify a perm here, so I guess I need an annoying xxyyxxyyxxy per x, which is now 3(11)+2(3)=39 qs.

At this point, the alternative strategy of using xyz instead of xyz to get your initial perms outperforms. (Note: the advantage is a reduction in number of perms, at the cost of a decent roll.) Here asking (eg) positions 012 and 210 clearly works, but without a roll requires 3(5) = 15 qs each, for a total of 2(15)+3 = 33 qs.

I don't feel like thinking about rolling right now, but who knows maybe it'll creep back into my head again. Oh well.

Best,
Eric

Title: Re: The Love Square
Post by James Fingas on Nov 28^th, 2002, 1:27pm

Eric,

I think that 30 questions is a very pessimistic estimate of how long it will take to find out the answer. This question is pencil-and-paper answerable--if you are a masochistic person with three or four sheets of paper ;)

As for a proof of optimality, I have a near-optimal solution with a small number of questions (approaching an order of magnitude smaller than 30). I might be able to shave one more question off by twiddling the possibilities, but I'm not sure yet.

Title: Re: The Love Square
Post by Eric Yeh on Nov 28^th, 2002, 2:00pm

Considering it is fairly easy to see that 7 is a weak lower bound (I'm pretty sure I could prove 8 if I wanted), even half an order of magnitude would be quite tough. But that's fine -- still pretty impressive. Like I said, I was only verifying your claim of existence, and haven't thought much about minimality.

Eric

Title: Re: The Love Square
Post by James Fingas on Nov 28^th, 2002, 2:09pm

Eric,

I would be very interested to see your proof that 7 is a lower bound ;D. Certainly there are different lower bounds based on what sorts of questions you ask. For instance, it takes more questions if you restrict yourself to binary information than if you always ask a person what their name is.

Title: Re: The Love Square
Post by Eric Yeh on Nov 28^th, 2002, 10:40pm

A-ha!!! I thought so. So maybe now you don't think 30 sounds so ridiculous (although I still concede it can probably be optimized somewhat). I was certainly assuming that only binary questions are allowed, as this is standard.

Eric

Title: Re: The Love Square
Post by James Fingas on Nov 29^th, 2002, 5:19pm

Eric,

I'm glad I told you I wasn't using binary questions--less confusion is better! Actually, I found it quite surprising that the "any question allowed" scenario is as difficult as it is.

Even with only-binary questions, you're not going to win any prizes with a 30-question solution. I only use two more questions with my binary solution than with my non-binary solution (the basic problem is not in getting enough bits of information, it's asking people in the most efficient order).

Title: Re: The Love Square
Post by Chronos on Dec 1^st, 2002, 10:09pm

Let me get this straight: A person will answer truthfully only if the conditions are met? That is to say, if the conditions are not met, then they're guaranteed to lie (unlike the love triangle, where they're trying to confuse you)? If that's the case, then I need only five binary questions (although I don't know if I can trim that down with non-binary questions). All I have to do is ask all five questions of the same person (say, U). Since I know I've never asked a question of U's sweetheart, U is guaranteed to lie to me, so I can reliably just invert all of U's answers. I then use any old binary tree to distinguish between the 24 possibilities.

Title: Re: The Love Square
Post by Eric Yeh on Dec 2^nd, 2002, 11:31am

Chronos,

Not that I am wildly supportive of this problem, but I guess I will respond since it is mildly defensive for me:

Precise wording aside, your interpretation is clearly not the intent of the author. The solution would be trivial and much of the set-up superfluous: those should be your first two clues. (You'd have to have a fantastically low opinion of both the author and myself to think that the intended meaning!)

You do bring up an interesting problem though: Find the minimum number of non-boolean questions one would require under your scenario. I'd classify this as nontrivial, but easy.

Eric

Title: Re: The Love Square
Post by James Fingas on Dec 2^nd, 2002, 12:54pm

Chronos,

Eric is right here--even it the conditions are not met, the subject may still answer correctly. Or so was my original intention, anyways.

In fact, if you want to argue like that, I should point out that I said "each person will only answer a question correctly if" the conditions are met. That is to say, when the conditions are met, then will only answer correctly. Funny wording, but technically it means exactly what I intended it to mean.

Besides, the subject could give meaningless answers to your questions too, or just swear at you (and not answer your question) ... I never ruled those possibilities out ;) Of course in the real "Love Square", a meaningless answer would be give you more information than a random answer, because you would know that the conditions weren't met.

Title: Re: The Love Square
Post by Chronos on Dec 6^th, 2002, 12:34am

OK, I thought that that was a mistake in the wording of the question (or maybe not a mistake, depending on how you parse "only":)), but I figured I'd hedge my bets, just in case you did mean that. Carry on.

Title: Re: The Love Square
Post by Eric Yeh on Dec 6^th, 2002, 6:14am

Fair enough.

BTW, I at some point found the 6Q soln, which I believe is optimal (but didnt check out the last two or so combos carefully).

I basically see how to do the boolean method in 8 but didnt take the time to verify. You basically get +1 for the loss of the three-way and another +1 to identify in the finale (i.e. requiring log 4 rather than 1 for a total of +1).

Best,
Eric

Title: Re: The Love Square
Post by James Fingas on Dec 10^th, 2002, 12:40pm

Here stood a hint--a tombstone dim.
Its cry: "Another puzzle dead!
The cause? A blow recieved from him;
I send it now to you instead."

The simplification I revealed
caused noble Forum-goers loss.
The trickiness of tricks repealed,
the gold of questing questions, dross.

But why do cruel tricks I play,
on these poor blameless puzzler kin,
when I instead my hand could stay,
and hold my answer still within?

Perhaps impatience swayed my mind.
With progress out of my command,
I sent a gauntlet, spiked, unkind
to lead these puzzlers by the hand.

Perhaps I yearned to lend defense
(my puzzle seemed a bit complex);
at lack of progress, took offense,
and other puzzlers chose to vex.

Perhaps it was just stubborn pride.
My riddle--what a simple task!
From only simple minds could hide
its secrets--a transparent mask.

The reason, as the case may be,
is lost in time and fickle mind.
The question-wish returns to me,
and hope that answers you will find.

So now I have removed the hint,
but cannot make amends to you.
Your knowledge I cannot untint;
your questions I cannot renew.

But learn, I pray, from my mistake!
The answer is for you alone,
lest from your friends this joy you take:
to find the answer on their own.

Title: Re: The Love Square
Post by Eric Yeh on Dec 10^th, 2002, 12:53pm

Well, that seems to me to be a huge clue -- but I suppose it's your prerogative.

Interesting -- in my soln it does take one longer to determine the "first part" in the boolean case, due to the fact that, as I mentioned, I employ one three-way elimination in the general case that requires two steps in the boolean case.

Title: Re: The Love Square
Post by James Fingas on Dec 10^th, 2002, 1:31pm

Humph, I thought you had given up on this one.

Sure, you can do a three-way elimination using non-boolean questions, but it doesn't gain you anything in the long run ... unless I'm missing something.

Title: Re: The Love Square
Post by Eric Yeh on Dec 10^th, 2002, 2:00pm

Given up? In what sense?? As I mentioned two posts ago, I'd already gotten the generalized soln at some point, and then figured the boolean one pretty much followed (as I wrote then). But after seeing your msg, I counted a little less nonchalantly and realized that the simple extension of my general soln to boolean has an extra +1, so it would actually have been 9Q.

Yes, I don't claim that using the three-way gives you better than 6Q (as I mentioned I virtually proved 6 was optimal, but left out two small sub-cases or so). I suppose I was just acknowledging that my prev boolean extension didnt actually clearly work in 8 rather than 9 as I claimed last time, though in my defense I devoted about one minute to that part.

Title: Re: The Love Square
Post by James Fingas on Dec 16^th, 2002, 10:31am

Sorry guys,

I apologize for ruining your fun by posting the answer to the "Love Square". After realizing how stupid I was being, I have modified my hint/answer.

Title: Re: The Love Square
Post by Eric Yeh on Dec 16^th, 2002, 11:04am

Yes, it's definitely not a great idea to post hints to your own puzzles. But don't feel too bad;
although I do agree that it was a big part of the soln (as I mentioned before). at least there is still a good amount of the puzzle that comes after it.

I'd actually say the first half was the more intuitive half, and certainly requires less grunt work than the second half (especially when it comes to proving optimality).

Best,
Eric

Title: Re: The Love Square
Post by Margit on Jun 9^th, 2003, 4:21am

Point of clarification.
Is the VERY FIRST question truthful ?

Title: Re: The Love Square
Post by Eric Yeh on Jun 9^th, 2003, 7:43am

Nope. It doesn't satisfy condition 1).

Title: Re: The Love Square
Post by Margit Schubert-.While on Jul 6^th, 2003, 5:35am

Well, what is the answer ? 6Q how ?

Title: Re: The Love Square
Post by wonderful on Mar 6^th, 2008, 9:27pm

Has anyone solved this fully? It seems very interesting.

Many thanks!