wu :: forums - Print Page


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

        riddles >> hard >> NEW PROBLEM:  The Gods of Gibberland
        
(Message started by: Eric Yeh on Aug 8^th, 2002, 2:09pm)

Title: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 8^th, 2002, 2:09pm

Hello everybody! After a four-year hiatus since "Past, Present, Future", this great new forum--so packed with people I have so quickly developed a great respect for--has inspired me to create a new series of puzzles! Here is one that I really like. :)

Caveat: This problem may sound impossible -- I should know, I spent many hours thinking about it and several variants, and at one point summarily rejected this proposal as having no possible solution! "What a cool one it would be," I thought, "if only it were actually solveable!!!" :D

What a great surprise it was, then, when I later had a revelation that seemed to provide a workable solution!!!!! However, I must admit that this problem, unlike PPF, comes to you guys with an insufficient amount of "playtesting". I've held back on posting it to try to get at least one independent confirmation of my solution, but none of my friends has yet been able to solve it! (In their defense, I only gave them a day or so to try it, and of course we all have work or something else to do...).

So there is always a possibility that there is some flaw in my solution, although I consider it highly unlikely. Even so, perhaps there would be another solution I hadn't thought of? So if you guys find it as interesting as I did, perhaps you can delve into it with me...

Without any further ado:

-----

THE GODS OF GIBBERLAND
There are three omniscient gods sitting in a chamber: GibberKnight, GibberKnave, and GibberKnexus, the gods of the knights, knaves, and knexuses of Gibberland. Knights always answer the truth, knaves always lie, and knexuses always answer the xor of what the knight and knave would answer.

Unfortunately, the language spoken in Gibberland is so unintelligible that not only do you not know which words correspond to "yes" and "no", but you don't even know what the two words that represent them are! All you know is that there is only one word for each.

With three questions, determine which god is which.

[Notes:

Standard: (Rules that are generally assumed unless otherwise noted.) The gods only answer yes/no questions. Each god answers in the single word of their language as appropriate to the question; i.e. each god always gives one of only two possible responses, one affirmative and one negative (e.g. they would always answer "Yes" rather than "That would be true"). Each question asked must be addressed to a single specific god; asking one question to all the gods would constitute three questions. Asking a single god multiple questions is permissible. The question you choose to ask and the god you choose to address may be dynamically chosen based on the answers to previous questions.

Specific: Because of possible loop conflicts, you may not ask any questions regarding how a knexus would answer.]

-----

Yes, this problem is designed to be anti-programming, anti-da/ya-algorithm, and besides that, beyond the traditional da-ya problem. I have written up some hints on it, but I don't want to hand them out quite yet... Who knows, maybe you'll all find it to be trivial! ;)

In any case, please let me know if anything is unclear!!!!! :D

Happy Puzzling,
Eric

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Drake on Aug 8^th, 2002, 4:01pm

It's unclear to me as to whether the Gods themselves behave like their worshippers.. In other words if you ask GibberKnave how a Knave would answer, would he lie about what the Knave would say (thus negating the Knave's answer)?

Or do the Gods always give a truthful answer?

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 8^th, 2002, 4:04pm

Sorry for the confusion; I guess I should have clarified: the gods behave as do their constituents.

Best,
Eric

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by bartleby on Aug 9^th, 2002, 8:28am

Knights always answer the truth, knaves always lie, and knexuses always answer the xor of what the knight and knave would answer.

OK, let me ask the obvious question: So if I ask them all the same question that has an answer of Yes, GibberKnexus will always answer something that means "Yes", then? Because if GibberKnight always answers Yes to my always-Yes question, and GibberKnave always answers No, then GibberKnexus will have to answer "Yes", right?

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 9^th, 2002, 8:33am

Often the case, yes! But not always. Observe: Are you a knight? ;)

Best,
Eric

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 9^th, 2002, 9:03am

Sorry -- just re-read your msg and realized I missed the part about asking a "yes" question. So the answer is that yes, a knexus would always respond "yes" to such a question.

Best,
Eric

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Drake on Aug 9^th, 2002, 11:33am

Darn you! I have not been able to stop trying to figure this one out since I read it last night.. It kept me up for a couple hours thinking about it. :o But I keep going in circles. I can solve it if I could ask 4 questions, but can't seem to do it in 3. If it were not for the language barrier this would be easy enough, but due to that you need to really figure out 4 pieces of information (the language, and the identities) with 3 questions.

I'm going to put down my reasoning thus far. Let me know if I'm on the right track or if I've taken a detour..

First, I'll refer to the 3 Gods as A, B, and C. I drew up a truth table based on their answers.

I started out thinking that the first thing to do is get a baseline for the language by asking A a question that he must respond No to. So I ask A, "Are you the God of the Knaves?" to which he must say No, and therefore I know the word for "No".

I then ask A a second question, "Are you the God of Knights?".

If he answers "No", then he must be GibberKnexus, as both the others would have said "Yes". It's then easy to figure the other 2 out by asking B, "Do knights ever lie?". If the answer to this is "Yes", the B is GibberKnave, and C is GibberKnight.

If A Answered "Yes" to the second question however, Then I'm stuck. This means A is either GKnave or GNexus, and either B or C is GKnight. I can then either figure out which is GKnight OR whether A is GKnave or GNexus with one more question, but I'm still left without knowing who the remaining 2 are.

I've also tried this without a baseline to get the language down.
I can ask A and B each "Do knights ever lie", then if the answer sounds the same, then the sound means "Yes", and C is GKnight. Then I ask A "Are you the god of Knights", to which he'll answer "Yes" only if he's GKnave.

But if the answer to the first 2 questioned sounded different, then I only know that A or B is GKnight, and that C is either GKnave or GKnexus. I could ask the same question to C and figure out which is the Knight and what "Yes" sounds like at the same time, but then I'm left without knowing who the remaining 2 are once again.

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Jonathan_the_Red on Aug 9^th, 2002, 11:38am

on 08/09/02 at 11:33:42, Drake wrote:

Darn you! I have not been able to stop trying to figure this one out since I read it last night..

It's a doozy, all right. My computer program has made no headway ;)

Quote:

I started out thinking that the first thing to do is get a baseline for the language by asking A a question that he must respond No to. So I ask A, "Are you the God of the Knaves?" to which he must say No, and therefore I know the word for "No".

This can't work. There are six possibilities for the arrangement of the Gods. If you spend a question getting the word for "No", you have to distinguish among those six possibilities with only four possible answer sets for the remaining two questions.

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 9^th, 2002, 11:41am

Sir Drake:

First, many thanks for your enthusiasm on my puzzle!!! I very much appreciate it!!!!! :) Did you also solve my last one? :)

Now, if you really want my help, here's a clue to the first mistake in your reasoning:

You cannot waste an entire question to determine tha language; it will not leave you with enough discriminating power.

Good luck!!!
Eric

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 9^th, 2002, 11:52am

Woops, I guess Jon got to that one before me! But I'm glad to know that I answered the right thing -- phshew! ;)

Glad to hear you are thinking about it, too, Jon; this one was for you! :D I was worried for a sec from your silence that I had offended you with my jokes! :P

BTW, how do you guys get the font color to precisely match the background? Even when I am "smart" enough to look and see which background my post will get, I haven't been able to find the right color schemes!!! I think I've seen you do it before perfectly, so that only a highlight illuminates the text?

Oh, and one last thing I meant to add to that last post to Drake: The god GibberKnight asked that I relay that he prefers to be called by his proper name rather than his position (even though you only did it once). ;)

Haha, ok so I'm in a weird mood just now.

Best,
Eric

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Jonathan_the_Red on Aug 9^th, 2002, 12:33pm

Eric--

Don't worry, I'm not easily offended ;)

To match colors exactly, you need to know what color you're matching... the color scheme on this board alternates between #252525 and #444444. So:

The below text is hidden on a dark background
Hi there!

The below text is hidden on a light background:
Hi there!

The source for both of these:

Code:

[color=252525]Hi there![/color]
[color=444444]Hi there![/color]

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Jonathan_the_Red on Aug 9^th, 2002, 12:34pm

Repeating earlier color code so you can see it on the different background:
The below text is hidden on a dark background
Hi there!

The below text is hidden on a light background:
Hi there!

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 9^th, 2002, 12:48pm

Excellent -- thanks dude. How'd you get the color scheme originally? O well, I'll remember it.

Ye, I guess I didn't really think you were offended, but I was disappointed that you weren't posting!!! ;)

So, any progress on the problem? :)

Best,
Eric

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Jonathan_the_Red on Aug 9^th, 2002, 12:56pm

Eric--

Originally, I got the scheme by trial and error. Then I viewed the source of the web page and found it there.

Here's where I am so far on your problem...

The first question cannot give you any immediate information (with the apparently sole exception of "Are you a knave?") Because of this, you can't really have any dynamic strategies between your first and second questions... before asking anyone anything, you pretty much have to choose your first two questions and whether to ask them to the same God or a different God.

Your first question obviously cannot reference either of the two "answer words". Your second question, however, must reference the answer word you get from the first question. Proof left as an exercise for the reader ;)

That's where I am so far. I'll keep chugging away.

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Joshua Franklin on Aug 9^th, 2002, 1:06pm

(I really need to stop reading riddles before I go to work) :P

I just spent 2 hours coming up with questions and possible answers and almost came up with an answer, but then realized that it wouldn't work, and then came up with this chart and THEN the questions.

Ask:

1. Would you lie to me?
2. Are you a God?
3. Are you GibberKnight?
4. Are you GibberKnexus?

GibberKnight GibberKnave GibberKnexus
1 No No No
2 Yes No Yes
3 Yes Yes No
4 No Yes Yes

I. Ask any god question 1 and 2.

Ia. If it replies 'No', 'No', then it is GibberKnave.

IbAsk a different god question 3. If it replies 'Yes', it is GibberKnight; if it replies 'No', it is GibberKnexus.

IIa. If it replies 'No', 'Yes', it is GibberKnight or GibberKnexus.

IIb. Then ask a different god question 4.

This is where I believe there is a problem with the riddle (or my logic). Because there are three people talking, if, after the first two questions, you don't know at least 1 of the gods, you are pretty much S.O.L.

I've followed my chart down every permutation, and if you start with either GibberKnight or GibberKnexus, and then move (or stay) to GibberKnight or GibberKnexus, because of the XOR, it becomes impossible (I think) to solve the problem. There will always be two Gods who answer in the same way, keeping the ambiguity.

I've been looking at this for 3 hours now, so I'm going to take a break and clear my head. I don't even know if I'm explaining myself well anymore--that's how muddled I am (try figuring out how GibberKnexus would answer: "Would GibberKnight answer 'Yes' to the question: 'What would GibberKnave tell me if I asked him if he was GibberKnexus'?") Lol, I thought it might help. :-)

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 9^th, 2002, 1:10pm

Jon, you're right on as usual. But now, riddle me this: Why are you Red??! ;)

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Jonathan_the_Red on Aug 9^th, 2002, 1:11pm

It's even worse, Joshua. The Gods don't answer "Yes" or "No", they answer in their own language, which you don't understand.

This puzzle really, really is tough.

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Joshua Franklin on Aug 9^th, 2002, 1:12pm

Spent so long writing my post I didn't see everyone else's...oh well, guess I gotta go back to the drawing board....

btw--where can I send a bill to eric and william for all the asprin I've had to buy since finding this site? :'(

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Joshua Franklin on Aug 9^th, 2002, 1:15pm

Jon,

I know that. That's why my first question established the word 'No'...Everyone answers 'No' to it, so I know what 'No' is, and if they say something different in the later questions I know it has to mean 'Yes'.

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 9^th, 2002, 1:28pm

Josh,

Thanks for your enthusiasm! Don't worry, you explain yourself well. Here's my response:

I agree that you are "SOL" if you have not identified one god after your second question. Hmmm. Actually, that's not true. But I will also be generous enough to say that my soln does identify one by two questions in. ;)

As for your concluding puzzle (which I like as a subpuzzle!), the answer is:

Yes.

Best of luck!
Eric

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 9^th, 2002, 1:31pm

on 08/09/02 at 13:12:52, Joshua Franklin wrote:

btw--where can I send a bill to eric and william for all the asprin I've had to buy since finding this site? :'(

Send it straight to Will -- I'm only a limited liability partner. ;) ;)

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Drake on Aug 9^th, 2002, 3:49pm

It's driving me MAD!!!

No matter how I work it, I can only get it down to knowing one of the Gods for sure.. The other 2 are always ambiguous.

Any hints for us, Eric? (BTW, that's my name too)
If I don't solve this today it's going to kill my weekend.. ;)

-- Eric

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 9^th, 2002, 3:55pm

Hmm, well, I do feel bad for you Drake, I really do. I think I am willing to help you out, but I don't want to give anyone else any clues. Thus, I cannot use this forum.

Send me an e-mail (eyeh@post.harvard.edu) so I have your address and I will respond to you directly -- under the condition that you never post any clues or solutions to the forum. (Only glowing words of praise -- haha jk.) :) ;)

Best,
Eric

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by tim on Aug 10^th, 2002, 12:27am

A small clue:
The price of knowing which god is which is that you can't always work out which word means what
That might just help someone. ;)

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 10^th, 2002, 10:48am

Tim,

Have you solved the problem? You'll be the first person I know. :D

Best,
Eric

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Joshua Franklin on Aug 10^th, 2002, 12:42pm

Haven't looked at the hint yet, only been thinking about the problem for 24 hours, maybe I'll look at it before I go to work. I'm not really closer to an answer...I think I need to get smacked upside the head so I start thinking differently. ::)

Eric--this problem is a marvel. The XOR really turns things around...would almost be easier if GibberKnexus answered randomly. :-) Thanks!

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 10^th, 2002, 1:00pm

Thanks dude!!! I really appreciate your support. I was pretty excited when I came up with the xor, too; it really shatters the standard da/ya construction! :)

Sorry to hear you have to work on a Saturday. (Nice pic btw! I came close to taking that one myself!)

Best,
Eric

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by icon on Aug 10^th, 2002, 5:30pm

eric what a riddle!

very nice, i spend some time on it and i didnt get anywhere far except i think the key is to have the 1st question based on the xor's answer so to speak i could be totally off but i go back to think :)

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 10^th, 2002, 7:24pm

Thanks Icon! Glad you are enjoying the riddle!! I am also honored to be graced by your first post as a true member -- that pic is totally you!

Best,
Eric

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by tim on Aug 11^th, 2002, 3:04am

I am pretty sure I have a general framework for solving it, but there is substantial ambiguity in the wording of the problem. I have used the framework to draw up three sample solutions, each with different interpretations.

The central problem is that when you say "knexuses always answer the xor of what the knight and knave would answer", how exactly does this work?

As one example, suppose the gods in positions 1, 2, and 3 are GibberKnexus, GibberKnave, and GibberKnight, repectively. Now you ask GibberKnexus "Is a knight in position 1?"

1) Knexuses answer the xor of "what the knight and knave would answer". If he were a knave, he would answer yes because it would be false. If he were a knight, he would answer yes because it would be true. Hence GibberKnexus should answer no.

2) If you actually ask any knave, he would answer yes. If you actually ask any knight, he would answer no. Hence GibberKnexus should answer yes.

Should he answer yes or no?

Basically, you use a counterfactual in the definition of the problem without defining the parameters under which the counterfactual is evaluated. There are actually a lot more than just two cases. That's why I have three solutions, and they don't come close to covering all the possibilities. :(

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Joshua Franklin on Aug 11^th, 2002, 9:30am

tim,

maybe i've been looking at that the wrong way, but when I come up with a question that I would ask them, I make a little chart and map out what the 3 gods would say...In your example:

Is GibberKnight in position 1 (no)?
GibberKnight says "no", GibberKnave says "yes", and therefore GibberKnexus would say "yes".

You shouldn't switch their physical positions to know what the XOR is; keep the same conditions for all 3 possible answers (+,-,XOR) and treat is more as a "what if".

I've been treating the XOR such as:

If both GibberKnight and GibberKnave would answer the question (regardless of if it is asked) in the same way (ie. Yes and Yes, or No and No), the XOR returns a False, or "no". However, if GibberKnight's and GibberKnave's answers differ (Yes and No, or No and Yes), the XOR returns a True, or "yes".

However, I still haven't come up with the answer so I could be doing it incorrectly too. ;)

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 11^th, 2002, 9:42am

Tim,

That is a great question; I wish you had asked it earlier so that I could clarifiy it for the other members of this forum -- although my own solution is independent of the answer! ;)

Your second proposition is the correct interpretation; if it were the first case I would have written "the xor of what he would answer if he were a knight and what he would answer if he were a knave." But you are right that there are some subtleties involved.

Here the definition is meant as the simplest possible interpretation, i.e., you get the xor of how each of a knave and knight would respond to the question. All "hard" references still refer lexically to the "true-life" situation, as in your example where "god 1" still refers to GibberKnexus. All "soft" references such as "you" in "are you a knight?" refer dynamically to the new persona. But only in the sense of identity! Everything else (e.g. position) still holds to true life, as if a virtual knight or knave shared all non-identity characteristics other than potential equivalence to hard references.

Example questions and answers with your set up:

1. Is god 1 a knight? (The example from your post.)
"Yes."
2. Are you a knight?
"No." (Though otherwise equivalent, there is a difference in scoping.)
3. Are you in position 1?
"Yes." (No change in position, which is a non-identity characteristic.)
4. Are you a knight and are you in position 1?
"No." (The virtual knight and knave would both answer "yes." Room for seeming paradoxes here
for the very very detail-oriented, but hey, it's more power to the people! And consistency is the
most important thing.)

Does that clarify all your questions? Does everyone agree that these rules are self-consistent (if sometimes seemingly paradoxical) and make intuitive sense? Again, I do not believe it affects the solvability of the problem, so I am writing here what my intuition was when I first wrote the problem.
(If the seeming paradoxes bother people, feel free to assume either fully lexical or fully dynamic scoping -- if I'm not missing something, they just make the problem harder anyway!)

Finally Tim, I'd love to see your solns -- off-line so as not to spoil it for the others, if you wouldn't mind. If that would be ok, please feel free to e-mail me (eyeh@post.harvard.edu). :)

Best,
Eric

PS Just read Josh's post, which sounds about right without going into some of the intricasies.

PPS Damn I can't stand this editor!!! The edit window, preview window, and true post window all have different horizontal buffers, so you can't figure out how to align split lines at all without officially posting!!! It's taken me several attempts just to get my question indents to line up, mostly because I first trusted the editor and then the preview! Any ideas?

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Jonathan_the_Red on Aug 14^th, 2002, 2:22pm

I haven't been able to dedicate many brain cycles to this problem lately (I do have a life outside of puzzles, unfortunately) but I'm starting to wonder if it's possible.

Potential proof of impossibility:

The first question gives you no immediate information, since you don't know what the word means. The second answer has two possibilities: same as the first, or different. Of the six possibilities in the solution set, the best you can do after two questions is divide them into two sets of three. (not that it's easy to do even that much.) There's no way that the third question, with only two possible answers, can produce a unique solution out of three possibilities.

Where am I going wrong here, Eric?

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 14^th, 2002, 2:38pm

Jon,

First of all, it's good to have a life outside of puzzles!!! ;) :D So don't worry, I'm not sitting here ticking away the clock so that when you post an answer I can finally declare that "it took Jon a whole ten days to do it"! ;)

Second, if it's any consolation, Tim has also found a solution, and also agrees with mine. So you can rest assured it's solveable.

Finally, where are you going wrong?

You can extract more information out of the first question, even if not immediately.

Let me know if you need more.

Best,
Eric

Title: Language Barrier
Post by Rupert on Aug 14^th, 2002, 3:06pm

While I haven't been able to solve it yet, how about a proof that it is unsolvable?

There are two kinds of answers:
1. Those which all gods would answer the same:
They give you no clue about who is who, but they solve the language problem. That leaves you with two yes/no answers which can produce four different results. Not enough for the six possible combinations of gods.
2. Those which not all gods would answer the same:
Having no knowledge of the language, the answers would be
one of the four combinations:
1. foo foo foo
2. foo foo bar
3. foo bar foo
4. foo bar bar
(assuming that you call the first answer you hear 'foo', the other one 'bar')
So, again, just four possible answers for six combinations.
Duh.

While this one would be pretty without the language issue, I don't see how it could be possible to solve. Did I misread something?

BTW: I still don't see how the language problem in PPF was solved (it was still hard enough without, though :-/): Jon's solution "Does 'splunge' mean 'yes' if and only if P?" doesn't work, unless you know beforehand that splunge means yes: If splunge doesn't mean yes, the answer will always be no. And, to be picky: If splunge does mean yes, the answer would still always have to be no, because splunge does not only mean yes when P, but it always means yes.
:P

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 14^th, 2002, 3:14pm

Rupert,

No, you did not misread anything, but you are missing a critical innovation for why your second "four combination" argument doesn't hold. Don't worry though, you're in good company -- only two people in the world have gotten it so far!!! ;)

Re: The PPF language problem: Note that the "iff" operator returns T on (F,F).

Best,
Eric

Title: Re: Language Barrier
Post by Jonathan_the_Red on Aug 14^th, 2002, 3:16pm

on 08/14/02 at 15:06:16, Rupert wrote:

BTW: I still don't see how the language problem in PPF was solved (it was still hard enough without, though :-/): Jon's solution "Does 'splunge' mean 'yes' if and only if P?" doesn't work, unless you know beforehand that splunge means yes: If splunge doesn't mean yes, the answer will always be no. And, to be picky: If splunge does mean yes, the answer would still always have to be no, because splunge does not only mean yes when P, but it always means yes.
:P

The truth table for "P if and only if Q" looks like this:

P Q P iff Q T T T T F F F T F F F T

If you want, you can think of it as "P is equivalent to Q." Or "(P if Q) and (Q if P)." Or "P XNOR Q."

Now, note that when P is true, the value of P iff Q is Q. When P is false, the value of P iff Q is (not Q). Let 'P' be the proposition that 'splunge' means yes. If P is true (i.e. splunge means yes), the correct answer to P iff Q is Q, meaning 'splunge' if Q is true, 'fleen' if Q is false. If P is false ('fleen' means yes, 'splunge' means no), the correct answer to P iff Q is (not Q), meaning 'fleen' (yes) if Q is false, 'splunge' if Q is true. In either case, 'splunge' is the answer if Q is true, 'fleen' if Q is false.

Sorry if this isn't very clear :-/

Oh, BTW, Eric: the "Red" in my name is a hair color thing :)

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 14^th, 2002, 3:26pm

I like my explanation better. I'm terse. ;) ;)

Gee Jon, it sure took you long enough to answer that one!! And from far away across threads, too!!! ;) Haha jk, tx for the response.

Best,
Eric

Title: iff
Post by Rupert on Aug 14^th, 2002, 3:40pm

Jon and Eric, thanks for explanation.

But that still requires you to know beforehand that 'splunge' is one of the possible answers, doesn't it?

But it also means that this riddle here might be solvable...

Must think...
it might...
wait...

I almost had it! ???

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 14^th, 2002, 3:42pm

That's right -- you do need to know that it is one of the possible answers in PPF.

'Gibberland' is different. ;)

If you get the answer, don't post it right away! E-mail me! :)

Best,
Eric

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Jonathan_the_Red on Aug 14^th, 2002, 5:11pm

Okay, so let's do a bit more thinking out loud...

Above, I argued that after the first two questions, you couldn't distinguish between getting AF and FA, nor could you distinguish between getting AA and FF. Apparently, that's incorrect :)

Setting aside for the moment the question of why that's incorrect, that still leaves four 'buckets' to sort the 12 possibilities into. No way to deal them out such that we can pinpoint the actual possibility with one more question. But there's an escape clause: we don't need to determine exactly which of the 12 is correct, because we can solve the problem without figuring out what word means 'yes' and what word means 'no'.

But in order for this to help us, we still need each bucket to have no more than two distinct possibilities... that is, two distinct arrangements of the three gods. Since some buckets must have more than two possibilities, that means that we need some questions that, given the same arrangement of Gods, would be answered the same regardless of which word means 'yes'.

Apologies if I'm not being very clear... it's been a long week and it's only Wednesday :-/ Let me try it like this:

Suppose the two words are 'arglebargle' and 'foofooraw'... again, you don't know either of these words prior to asking any questions. Label the gods T, F, and X. Label the 12 possibilities for god arrangement + meaning of 'arglebargle' like so:

TFXY
TFXN
TXFY
TXFN
FTXY
FTXN
FXTY
FXTN
XTFY
XTFN
XFTY
XFTN

Now, you have four buckets labeled 'A A', 'A F', 'F A', and 'F F', representing the answers you get for the first two questions you ask. Each of the 12 possibilities must go into one and only one bucket. Each bucket can contain no more than two possibilities that differ in their first three letters.

The conclusion from the above is that at least two buckets (and possibly all four) must contain multiple possibilities that differ only by last letter. These represent questions that given gods would answer the same way no matter what 'arglebargle' means. I certainly hope there's a flaw in this reasoning, because I see no way to do this :(

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Jonathan_the_Red on Aug 14^th, 2002, 5:19pm

By the way, I hope this puzzle doesn't involve trickery like the below:

Ask God A: Is this sentence true if and only if God A is a Knexxus?

Neither a knight nor a knave could give any answer at all, while a Knexxus would answer Yes.

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by AlexH on Aug 14^th, 2002, 5:38pm

Jonathan: Good analysis, but you're giving up too early. Consider using arglebargle or foofooraw in your questions.

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 14^th, 2002, 6:03pm

Jon,

I agree with the first half of your first msg. Re: the second half, your last paragraph is flawed. There is no flaw in your other logic, but there is still a soln!

Re: your second msg, no, I don't use such treachery! Note to self: add "no self-referential questions" to standard rules.

Alex,

do you have the soln?

Best,
Eric

Title: Brainstorm
Post by Rupert on Aug 14^th, 2002, 8:44pm

Argh -- this is driving me nuts. It's 5:20 in the morning now and I can't sleep.
Still no solution, but some more thoughts / assumptions / summary.
Please tell me if I'm already wrong here:

a) For starters, forget the whole Truth/Lie/Xor thing. Just assume they all tell the truth. Doesn't exactly make it easier, but a little less mind warping.

b) We cannot afford a whole question just to find out what yes/no means.

c) We cannot solve without ever finding out what yes/no means.

d) For questions 2 and 3, we could get yes/no answers (Using Jon's iff technique), but that still doesn't mean we know what the answer to Q1 was.

So somehow, we need questions that contain information about both: positioning and yes/no meaning. (3 questions give 8 possible outcomes. We need only six combinations. So somehow 1/4 of every answer should go towards solving yes/no. That's a 3/4 answer all in all. Whoa. I need sleep.)

One idea I had was letting the gods XOR their answer to Q2,Q3 with our assumption about whether A1 meant yes or no. But so far it's just that. An idea.

Night.
:P

Title: Re: Brainstorm
Post by Jonathan_the_Red on Aug 14^th, 2002, 8:57pm

on 08/14/02 at 20:44:45, Rupert wrote:

a) For starters, forget the whole Truth/Lie/Xor thing. Just assume they all tell the truth. Doesn't exactly make it easier, but a little less mind warping.

Well geesh, that would make it a whole lot simpler :)

Define the relation "reliability" such that GibberKnight is more reliable than GibberKnave is more reliable than GibberKnexus.

Q1: Is 2+2 equal to 4?
Q2: Are you more reliable than that guy?
Q3: Is that guy more reliable than that other guy?

Quote:

c) We cannot solve without ever finding out what yes/no means.

I don't think this is the case. In fact, I'm pretty near certain that in at least some cases we will figure out which God is which without knowing what yes/no means.

Quote:

One idea I had was letting the gods XOR their answer to Q2,Q3 with our assumption about whether A1 meant yes or no. But so far it's just that. An idea.

Interesting idea. I'll mull it.

While I'm at it, I want to run something by Eric:

(hidden)

I'm exploring possibilities for the first question that involve things like "P if and only if the word for 'yes' is alphabetically before the word for 'no'" I don't want any hints on this yet, just wanted to say I'm exploring it :)

(end of hidden)

Quote:

Night.
:P

Get some sleep :)

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 14^th, 2002, 8:58pm

Rupert,

Sorry to cause you so much trouble!!! Where are you, then, London?

a) A good primer for the first innovation, I agree. :)
b) True.
c) False.
d) True and True.

Best,
Eric

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 14^th, 2002, 9:02pm

Erg, you always beat me to the post!! :P :)

Ok then Jon, thanks for the update. No hints from me. ;) Enjoy the exploration!

Best,
Eric

Title: Re: Brainstorm
Post by Jonathan_the_Red on Aug 14^th, 2002, 9:11pm

Quote:

d) For questions 2 and 3, we could get yes/no answers (Using Jon's iff technique), but that still doesn't mean we know what the answer to Q1 was.

BTW, that bastard GibberKnexus completely blows away the iff technique. Take a simple proposition P and ask a Knight or a Knave "does plonk mean 'yes' if and only if P", and the Knight will answer plonk if P is true and blatz otherwise, while the Knave will answer blatz if P is true and plonk otherwise. The Knexus, though, will answer whichever word means yes. No longer does the iff technique break through the language barrier.

Title: Re: Brainstorm
Post by Rupert on Aug 15^th, 2002, 4:25am

on 08/14/02 at 20:57:32, Jonathan_the_Red wrote:

Define the relation "reliability" such that GibberKnight is more reliable than GibberKnave is more reliable than GibberKnexus.

Q1: Is 2+2 equal to 4?
Q2: Are you more reliable than that guy?
Q3: Is that guy more reliable than that other guy?

If the answer to Q3 is no, you're done. But if it is yes, you still don't know if 'that other guy' is between 'you' and 'that guy' or if he is more reliable than 'you'. -- i.e. the order established by Q2 leaves three 'emtpy spots' from which we would have to decide by just one question.
I hope that I'm wrong here, because that would make it easier, but I'm afraid I' not.

Quote:

I don't think this is the case. In fact, I'm pretty near certain that in at least some cases we will figure out which God is which without knowing what yes/no means.

I came up with many solutions that work in some cases ;). I meant that a
general solution would have to include finding out what yes/no means.

BTW, I dreamt of this! I was in a cafeteria with two waiters, one of them needed to be lied to, the other needed the truth...

Title: Re: Brainstorm
Post by Rupert on Aug 15^th, 2002, 4:48am

on 08/14/02 at 21:11:01, Jonathan_the_Red wrote:

Good one. I didn't notice that. Well, not good, really. >:(

What if I asked a question like "If you are Knexus then Qa, otherwise Qb"? Would Knexus answer Qa or Qb? Eric?
(I'm afraid I won't like the answer... :-/)

Cheers

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Rupert on Aug 15^th, 2002, 4:55am

on 08/14/02 at 20:58:02, Eric Yeh wrote:

c) False.

Thanks Eric,

Hm. Do you mean there are certain paths where we don't need to find out (this is what I understand Jon meant), or is it generally not necessary? (Don't answer if it gives away too much)

(I'm in Germany)

Title: Re: Brainstorm
Post by Eric Yeh on Aug 15^th, 2002, 5:25am

on 08/15/02 at 04:25:18, Rupert wrote:

Ye, I'm afraid I have to agree that if I understand it correctly, I don't see how it bypasses the language barrier.

on 08/15/02 at 04:25:18, Rupert wrote:

I came up with many solutions that work in some cases ;). I meant that a
general solution would have to include finding out what yes/no means.

Actually, Jon meant that he believes that in any ONE solution that works for all cases, there will be SOME "cases" (defined by sequences of answers) in which you cannot resolve the words for "yes" and "no", whereas with certain other "cases" you will be able to deduce the meanings.

on 08/15/02 at 04:25:18, Rupert wrote:

BTW, I dreamt of this! I was in a cafeteria with two waiters, one of them needed to be lied to, the other needed the truth...

Cool!!! :D But where's GibberKnexus?? ;)

Best,
Eric

Title: Re: Brainstorm
Post by Eric Yeh on Aug 15^th, 2002, 5:29am

Oops, didn't see this new page!

on 08/15/02 at 04:48:39, Rupert wrote:

Sorry: yes-no questions only, as per the standard rules. ;)

on 08/15/02 at 04:55:48, Rupert wrote:

Yes, paths.

Best,
Eric

Title: Re: Brainstorm
Post by Rupert on Aug 15^th, 2002, 5:48am

on 08/15/02 at 05:29:57, Eric Yeh wrote:

Sorry: yes-no questions only, as per the standard rules. ;)

Qa Qb were supposed to be some question. As in "If you're Knexus, is A Knight, otherwise is 5=7?"
But Knexus really would have to answer to 5=7 as I understand it. So it doesn't help anyway...

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 15^th, 2002, 5:50am

Correct. Sorry I misunderstood your earlier message.

Best,
Eric

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Rupert on Aug 15^th, 2002, 8:48am

Maybe this is just some psychological experiment to find out how long you can convince someone to work on a problem to which there is obviously no solution just by claiming there is one?

:P

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 15^th, 2002, 10:40am

Oh oh, you've got me!!! I myself am working on a open-ended problem from another puzzle web site: "Model the average length of time spent by strangers on a newly created impossible problem as a function of the credibility of the author. Determine the amount of credibility which maximizes that length of time."

Unfortunately, I am not bright enough to solve this on my own, so I am forced to study the problem empirically. A couple of years back I tried using credibility = 0; now I am experimenting on using credibility = 1 solveable new problem. Failing this, I will try again in a couple of years by first issuing two solveable problems, and go from there.

Best,
Eric

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Rupert on Aug 15^th, 2002, 11:35am

Ha! I knew it.
Nice touch btw to get Tim to indicate that he found the solution.

Now where's my tinfoil hat?

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 15^th, 2002, 11:40am

Ye, we are all in on it together! Jon is only pretending he's looking for a soln.

Sorry, what's this hat thing? Is this some German reference I'm missing?

Evilly yours,
Eric

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Rupert on Aug 15^th, 2002, 12:12pm

on 08/15/02 at 11:40:48, Eric Yeh wrote:

Sorry, what's this hat thing? Is this some German reference I'm missing?

Tinfoil hats keep aliens/black helicopters from reading your mind and/or remote controlling your brain.
You mean you don't have one? ;)
But then again, you are probably sitting IN the black helicopter.
And I shouldn't have told you...

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 15^th, 2002, 12:14pm

Say, is that Illuminati???!!

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Jonathan_the_Red on Aug 15^th, 2002, 1:05pm

Don't have much time (that stupid 'real life thing')... just wanted to pop in and acknowledge my error earlier re. the simpler problem where the Gods all tell the truth. Sigh...

Here are three questions that really do work in that case.

(hidden color to prevent spoilage)

Ask God A:
Q1: Is the word that means "yes" alphabetically before the word that means "no" if and only if you are GibberKnight?

God A answers: "foon".

Ask God A:
Q2: Does "foon" mean "yes" if and only if you are GibberKnave?

Case 1: God A answers "foon". In this case, he is GibberKnave
Case 2: God A answers "blatz". In this case, he is GibberKnexus
Case 3: God A answers "worple". In this case, he is GibberKnight.

For Q3, just use the iff trick to ask about one of the two gods you don't know.

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 15^th, 2002, 1:09pm

Without checking the details, yes, something like that would work. Good job Jon!

Perhaps you want to put it in [colors] so prevent spoilage? :)

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Jonathan_the_Red on Aug 15^th, 2002, 1:15pm

Good idea. Just so I'm clear, the above solution works only if all three Gods tell the truth... but I'm pretty sure that it can be modded to work for the "real" case. I'll poke away at it this weekend.

BTW, this is not at all a big deal, but I prefer Jonathan to Jon. Just FYI.

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 15^th, 2002, 1:19pm

Ye ye, I knew that. If it were the real deal I would've checked it a little more carefully!! :) Ye, the expansion requires a "second innovation" to get the knexus personality to fall in line, but you're certainly on the right track.
But Jonathan is too long to type!!! What will happen if I keep calling you Jon? You said you were difficult to offend, after all!!!!! ;)

Best,
Eric

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Rupert on Aug 15^th, 2002, 1:58pm

Hm. Relying on alphabetical order would be less than elegant.
Not only because of ambiguos sounds like e.g. s/c or h/j in some languages. What about that African toungue-popping consonant, or what if 'no' sounds like shattering glass and 'yes' sounds like a trumpet? These guys are some weirdo GibberGods after all, and "the language spoken in Gibberland is so unintelligible [...]".

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 15^th, 2002, 2:01pm

This is true; "better" (i.e. more universal) conditions that accomplish similar things can be found.

Rupi, didn't I tell you not to read that msg??! ;)

Best,
Eric

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Rupert on Aug 16^th, 2002, 3:19pm

Hi Eric,

I didn't get your mail until after I read the comment. But I actually found it to be more of a distraction than a hint. So no harm done. ;)

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 16^th, 2002, 4:05pm

Fair enough. Sorry I haven't gotten a chance to look carefully at your msg yet (tho things fine); been a bit busy at work.

Best,
Eric

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Jonathan_the_Red on Aug 16^th, 2002, 6:43pm

As Aristotle said when he entered his bath, "Fabreka!" (literally, "I have found the fabric softener!")

I'm not terribly thrilled with this solution (I find it a bit clunky), but it does work (*). Hidden with color tags... DO NOT HIGHLIGHT IF YOU DON'T WANT TO SEE A SOLUTION

-----

Ask God A: "Does the word for 'yes' come alphabetically before the word for 'no'?"

GibberKnight will say whichever answer word comes alphabetically first. GibberKnave will say whichever answer word comes alphabetically second. GibberKnexus will say whichever answer word means 'yes'.

Ask God A: "Does the word for 'no' come alphabetically before the word for 'yes'?"

If the answers to the two questions are the same, God A is GibberKnexus, and his answer means 'yes'. Ask God B: "Is 2+2 equal to 4?" If his answer is the same as God A's answers, he's the Knight, otherwise he's the Knave.

If the answers to the two questions differ and the answer to question 1 precedes the answer to question 2 alphabetically, he's a Knight. If the answer to question 2 precedes the answer to question 1, he's a knave. Either way, you can use the iff trick combined with the "what would you say if I asked you..." trick to determine which of the other Gods is which.

-----

That was quite a doozy. More commentary below hidden by color...

-----

The key to this one, of course, is to come up with a question that will force a Knight to give one of the answer words and a Knave to give the other, regardless of which word means 'yes' and which means 'no'. I used alphabetical order for the purpose... if there's a cleaner way, I'd like to know it.

-----

Thanks, Eric, for the hours of mental exercise :)

(*) At least, I think it works. If not, wouldn't be the first time I've been mistaken when I thought I had a solution...

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 16^th, 2002, 6:59pm

Nice job Jon!! Ye, that is pretty much it! I'm not sure why you call it 'clunky'; I think it's pretty good! The first two questions make it truly elegant!!!

Something hidden:

Yes, the alphabet part is potentially problematic because they don't have to use an English alphabet, and even if they do there's no guarantee that you will be able to recognize their pronunciation. But you certainly have the right spirit. I think the most universal proposition to use is "The word I would find more aesthetically pleasing immediately after hearing the second word..." This taps the omniscience of the gods, but hey, omniscient is omniscient!!! And there's no arguing that it will have an answer which the questioner will know. Satisfactory, I hope? :)

OK then, I will wait a little bit more for last answers to trickle in, and then maybe post a breather or so before moving on!!! :D

Best,
Eric

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Rupert on Aug 16^th, 2002, 8:12pm

Jonathan,

I'm surprised that it is possible after all with such simple questions. (The solution I came up with has questions about 8 lines long when written out in plain English.) -- I'll let you see in a private message.

Good job.

Rupert

Title: Proposed Extension to Riddle
Post by Rupert on Aug 17^th, 2002, 9:28pm

How about an extension to the riddle?

You may not speak to the Gibbergods directly, but rather you have to relay your questions through a herald. You must tell him all three questions at once. Unfortunately, he is rather confused. He is neither able to select from several questions depending on previous answers, nor does he remember which of the gods he was supposed to ask which question. I.e. all he can do is repeat the three questions in the right order, randomly addressing one of the gods for each question.

8)

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 17^th, 2002, 10:13pm

Rupi,

It's a good initial thought, but in the end not a good idea. The "problem" with stating the problem that way is that it reduces the search space too much, thereby actually making the problem easier to solve. That is why I have only been challenging people to do it that way after they give me a first soln.

Best,
Eric

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Rupert on Aug 17^th, 2002, 10:30pm

on 08/17/02 at 22:13:10, Eric Yeh wrote:

The "problem" with stating the problem that way is that it reduces the search space too much, thereby actually making the problem easier to solve.

You are right. If at all, it should be a 'second round' add-on.

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 18^th, 2002, 8:15am

Glad you agree -- didn't want to offend you!! `:)

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Jaberwock on Aug 29^th, 2002, 8:32am

Finally!!!!
I've been working on this problem on and off for the last few weeks and finally solved it. Thank you for such a challenge! I ended up with roughly the same solution as Jonathan, although I think I took a longer path to it. ;D

I started of with compound questions, hoping that I could extract the language by the end, but that was obviously a dead end. I then realized that I would need to differentiate between the answers (like Jonathan did), but I was still thinking of compound questions, like "Is T < F AND are you the Knexus...". After a lot of truth tables I realized that simpler could be better. :D

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 29^th, 2002, 8:42am

Congratulations Jaberwock! Glad you enjoyed the puzzle!!! And yay, another newly registered user honoring my thread with his first post. :)

By the way, don't you want another b in your name?? ;)

Best,
Eric

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Jabberwock on Aug 29^th, 2002, 8:49am

Grr... should have payed more attention before I created that. Now it should show up correctly but I have to remember to login with the misspelled version. :'( But anyway, I'm gladd to finally be a member after the past month of lurking.

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Aug 29^th, 2002, 8:53am

Heh -- gd for you. I like your pic -- is that your own? I don't remember seeing it as a choice.

Have you looked at my other two currently posted problems? :)

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Jonathan_the_Red on Sep 10^th, 2002, 2:19pm

Hey, Eric, do you mind if I share this puzzle with some Microsoft folks? Giving full credit where it is due, of course.

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Sep 10^th, 2002, 2:58pm

That would be fine -- I appreciate your asking! So you work at MSFT eh?

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Oct 12^th, 2002, 4:24pm

So Jon, following up: what'd the MSFT ppl think?? How's the puzzle comp?

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Jonathan_the_Red on Oct 12^th, 2002, 8:46pm

To tell you the truth, Eric, nobody responded when I sent the puzzle to the Puzzle Hunt mailing list... although at least one person, Garzahd, was drawn to this group because of it. At least a couple of my personal acquaintances are working on the puzzle right now.

The Puzzle Hunt was a rousing success... my team finished a semi-respectable seventh out of about 45. Next year we'll do better. (We would have placed higher, except we solved a critical meta-puzzle with less than two minutes to go in the hunt and didn't have time to submit our answer.)

The organizers have asked that we not post the puzzles outside of Microsoft until some copyright issues are cleared up... if/when they clear us, I'll put them up somewhere they're accessible to this group. The puzzles were (IMHO) of mixed quality... some of them were fairly uninspired, but others were gold. Many of them cannot be solved without access to internal Microsoft sites or the Microsoft campus itself, and others require physical items (decks of cards, lengths of cord) that were provided to us.

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Oct 12^th, 2002, 10:49pm

Aw, that is too bad. :( Well, glad at least some others are working on it.

Congratulations on your "semi-respectable" finish! Sounds like it was a lot of fun. I will look forward to hearing some of these "gold" questions. ;) ;)

Best,
Eric

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by carpao on Jun 22^nd, 2004, 3:10pm

on 08/16/02 at 18:43:05, Jonathan_the_Red wrote:

DO NOT HIGHLIGHT IF YOU DON'T WANT TO SEE A SOLUTION

-----

Ask God A: "Does the word for 'yes' come alphabetically before the word for 'no'?"

GibberKnight will say whichever answer word comes alphabetically first. GibberKnave will say whichever answer word comes alphabetically second. GibberKnexus will say whichever answer word means 'yes'.

Ask God A: "Does the word for 'no' come alphabetically before the word for 'yes'?"

If the answers to the two questions are the same, God A is GibberKnexus, and his answer means 'yes'. Ask God B: "Is 2+2 equal to 4?" If his answer is the same as God A's answers, he's the Knight, otherwise he's the Knave.

If the answers to the two questions differ and the answer to question 1 precedes the answer to question 2 alphabetically, he's a Knight. If the answer to question 2 precedes the answer to question 1, he's a knave.

Either way, you can use the iff trick combined with the "what would you say if I asked you..." trick to determine which of the other Gods is which.

I'm missing the last passage...
If we had two different answer at the first two question I agree that we can understand who is the questioned god by examine the order...
but we have no indication of what is the word for "yes" and what is the word for "no"...

So finally how we can understand the last two gods?

If we make a question where both must answer the same... it is clear that we cannot distinguish them...
but if we make a question where they must answer differently... we (not knowing what is yes and what is no) cannot distinguisj again...
probably we have to introduce in the iff clause a dependency on a binding of 'yes' with one of the "heard words"...
but could someone help me in understanding the last question?

thanks

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Three Hands on Jun 22^nd, 2004, 3:35pm

The cunning part is that, through knowing who the god you are questioning is, you can then remember the answers given in order to say what the terms for "yes" and "no" are (except in the case of GibberKnexus, but then you only know what the term for "yes" is, and so could presumably deduce what "no" is). If you have worked out that GibberKnight answered, then the first answer means "yes" and the second answer means "no". If you were asking GibberKnave, then the first answer means "no" and the second answer means "yes". Therefore, assuming you remember which word is which, you can translate the subsequent answers.

Oh, and belated congratulations to Jonathan - only just seen this thread, and having seen the answer you reached, I can only say it's an answer I would have struggled to reach (if I reached it at all!!!!)

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Leonid Broukhis on Jun 22^nd, 2004, 7:27pm

This answer is very hard to reach indeed, because the ability of the visitor to perform a lexicographic comparison (whose result matches the gods' result) does not follow from the problem statement. The only ability that does naturally follow is the ability to perform an equality comparison.

What if the gods understand English but respond in Chinese?

As the trick is in asking a question about a property of the responses that is "computable" by the visitor, what is such a property of an audio sample?
The questions about a totalistic property (duration, average frequency, etc.) are out, because the two samples can have equal totalistic properties, but what is the best (simplest) dynamic property?

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Jun 22^nd, 2004, 8:20pm

Leonid,

It is true that the precision of Jonathan's "lexicon" solution of yesteryear is slightly debatable. But as it was so close to the originally conceived solution, I had let it pass with hearty congratulations. But perhaps it is finally time to close this minor little hole.

To be more precise, one simply needs to assert that the asker create any total ordering on the set of all possible responses. For example, this may be a function which maps the set of all possible sounds to the real axis. Although there are arbitrarily many ways to create this function -- one of which can be extended by a lexicographic type of argument a la Jonathan's -- my original and still favorite way to conceive of this (which in my mind remains incredibly intuitive and irrefutable) is a function whereby "A > B" iff "I like the sound of A better than the sound of B."

Once you believe that a fixed ordering exists, note that the Gods, being omniscient, know whether A > B or B > A, where A and B are their words for yes and no. Then substitute "A > B" for "A earlier than B" in Jonathan's argument, and you are done. [As before, you need to be sure that the responses of AAA and BBB, if they arise at all, imply the same ordering of gods.]

Hope that solution is satisfactory to all my readers here! Thanks again to everyone for their interest!!! :)

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by BNC on Jun 22^nd, 2004, 10:08pm

Hi Eric,

We hardly see you around -- glad you drop by from time to time! ;D

As for the "like the sound" approach, I'm not sure if it's guaranteed to work. Even assuming that the mapping of all possible sounds to the "like" axis is one to one, the two sounds may be arbitrary close to each other.

So the omniscient gods can tell that "snift" is slightly more likable to you than, say, "snuft". But in your mind, they may be undistinguishable close.

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by carpao on Jun 23^rd, 2004, 2:52am

on 06/22/04 at 15:35:11, Three Hands wrote:

If you have worked out that GibberKnight answered, then the first answer means "yes" and the second answer means "no". If you were asking GibberKnave, then the first answer means "no" and the second answer means "yes". Therefore, assuming you remember which word is which, you can translate the subsequent answers.

one moment to think

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by carpao on Jun 23^rd, 2004, 3:04am

on 06/23/04 at 02:52:23, carpao wrote:

one moment to think

I don't agree with that...

let me make a counterexample:
if they speak italian yes is "SI" and no is "NO"
now to the question:
does the translation("yes") precedes translation("no")?
the gibberknight answers:
NO
and to the question:
does the translation("no") precedes translation("yes")?
the gibberknight answers:
SI

because the NO precedes SI I understand that it is Gibberknight, but as you can see the first answer is the translation of "no"...

To be complete, let consider the other case:
if the translation of "yes" is "ASI"
now to the question:
does the translation("yes") precedes translation("no")?
the gibberknight answers:
ASI
and to the question:
does the translation("no") precedes translation("yes")?
the gibberknight answers:
NO

this time the first word is the translation of "yes"
(again I can however still identifies the god as GibberKnight from the fact that ASI precedes NO)

So after the two questions I am able to identify the god that I asked, but (if he is not GibberKnexus) I don't know what are the binding from yes and no to their translation

So... what is the solution for teh last question?

BTW if it was true that I had also te binding of the translation the last question is very simple and exactly of the form:
is true equal to false?
or
is true equal to true?
(dependent from who was the the identified god)

so it would not require the "iif" (if and only if) and complicated form proposed in the original solution...

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by rmsgrey on Jun 23^rd, 2004, 5:49am

So you've established that the words for yes and no are X and Y (in some order), and that you're talking to someone who is always truthful (or always lies - but you know which)

So you need a question that the (known) truthful deity, A, will answer differently depending on whether B is the liar or the knexus, but the same way regardless of which of X and Y is yes.

::[hide]
If I were to ask you whether B is the Gibberknexus, would your answer be X?
[/hide]::
Analysis:
::[hide]
If B is knexus, and X is yes, then A would answer X(yes) to the inner question and so answers X(yes) to the whole question.
If B is knexus and X is no, then A would answer Y(yes) to the inner question, so answers X(no) to the whole question.
If B is not knexus, X yes, then A would answer Y(no) to the inner question, so answers Y(no) to the whole question.
If B is not knexus, X no, then A would answer X(no) to the inner question, so answers Y(yes) to the whole question.

Similarly, if A is known to be the liar, then the same question produces the same answers, for example:
If B is knexus and X is yes, A would falsely answer Y(no) to the inner question, so falsely answers X(yes) to the whole question.
[/hide]::

See the "transylvanian fork in the road" and "another fork in the road" threads for a simpler knight/knave type problem with an unknown language.

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Jun 23^rd, 2004, 6:41am

BNC,

Haha thanks -- I still keep watches over the threads I always watched (too lazy to change those settings!); I don't necessarily check all of them, but I definitely read messages for the ones I've created. Not usually a lot of activity though :( Hahaha.

To address your concern: Yes, clearly there is a requirement that you need to be able to distinguish the answers for yes and no. Beyond that, it is up to you to convince yourself that given any two sounds, you can find a function that totally orders them. A cool result is that you don't actually need to be consistent among different sets of sounds, eg, you dont actually need transitivity. You only need antisymmetry.

Well, at some point the debate becomes semi-philosophical, and I do apologize to you or anyone else who finds this sollution unsatisfying. I toyed with the idea of having the gods speak in strings of English letters etc, but it just made the problem much less believable sounding in a way that, to me, not only detracted from the elegance of the problem statement, but also gave an automatic clue to the solution (though it is far from full!). In the end, I chose the route that I knew would be slightly more controversial in this metaphysical sense, but luckily I have had no challenges till now :)

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by carpao on Jun 23^rd, 2004, 7:15am

on 06/23/04 at 05:49:23, rmsgrey wrote:

...
So you need a question that the (known) truthful deity,

THANKS A LOT this was the point
I was so stupid that I looked for a question to ask to one of the other two gods...

;D

for Eric... thanks for this beautiful riddle...

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Jun 23^rd, 2004, 7:38am

many thanks carpao!!! those little notes really mean a lot to me!!! :D :D

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by rmsgrey on Jun 23^rd, 2004, 7:43am

If you can't distinguish between "yes" and "no" when you hear them, then you can't get any information at all. So for the problem to be at all solvable, you need to be able to distinguish between the two words, so all you need to be able to do is come up with a system which, given any pair of words orders the pair in the same way each time the same pair come up (regardless of the order in which they appear). You don't even need to know the function explicitly yourself - it just needs to be a reliable "black box" provided the deities omniscience applies to it.

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Stinkbeard on Nov 12^th, 2007, 9:06am

Maybe the gods can answer in musical tones? That seems a very godly way to communicate.

Q1: Is your word for yes a higher pitch than your word for no?

Q2: Is your word for yes a lower pitch than your word for no?

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Tasselfoot on Mar 24^th, 2008, 3:46pm

I posted a new thread for this, so my apologies if bumping this in addition is frowned apon.

I am curious as to 3 questions to ask based upon a 3rd deity that responds randomly instead of XOR.

I assume that it is all VERY similar, but frankly, trying to comprehend the responses of the deities, even on paper, gives me a massive headache.

So any assistance would be most appreciated, as this is a problem posed to a group of us on another site.

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by temporary on Mar 27^th, 2008, 7:20pm

on 08/09/02 at 11:41:54, Eric Yeh wrote:

Yes it will, and it is required. You need 1 question for the language, and 2 for the "discriminating" which determines the 3 of them with process of elimination. Just like with the 3 ghosts where 1 lies, 1 truths, and 1 is random, you use 1 question to make sure you aren't asking the random 1 next.

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by Eric Yeh on Apr 7^th, 2008, 6:07pm

depends on what you mean for the language then. if the first q tells you "a little more than" just the language, then it is possible. but if not, two questions is not enough to discriminate btwn all three. two questions gives 2^2 = 4 possible answers, but there are 3! = 6 permutations of the gods.

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by i_kvikrant on Jan 19^th, 2012, 9:47am

Sorry for being a late poster on such an old thread.
This is one of the best puzzle I have ever seen.
I came across this riddle on the page where other such riddles are posted , i.e on
http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml

Quote:

There are three omniscient gods sitting in a chamber: GibberKnight, GibberKnave, and GibberKnexus, the gods of the knights, knaves, and knexuses of Gibberland. Knights always answer the truth, knaves always lie, and knexuses always answer the XOR of what the knight and knave would answer.

Unfortunately, the language spoken in Gibberland is so unintelligible that not only do you not know which words correspond to "yes" and "no", but you don't even know what the two words that represent them are! All you know is that there is only one word for each.

With only three questions, determine which god is which.

Note 1: What follows are standard rules that are generally assumed unless otherwise noted. The gods only answer yes/no questions. Each god answers in the single word of their language as appropriate to the question; i.e. each god always gives one of only two possible responses, one affirmative and one negative (e.g. they would always answer "Yes" rather than "That would be true"). Each question asked must be addressed to a single specific god; asking one question to all the gods would constitute three questions. Asking a single god multiple questions is permissible. The question you choose to ask and the god you choose to address may be dynamically chosen based on the answers to previous questions. No self-referential questions (e.g. "is this question true iff ...").

Note 2: Because of possible loop conflicts, you may not ask any questions regarding how a knexus would answer.

I am having trouble understanding what is meant by
" No self-referential questions (e.g. "is this question true iff ..."

Is the puzzle being discussed in the present thread subtly different from the one on the riddles website?
Because, in this thread people seem to have used iff questions to solve the puzzle. Right ?

Title: Re: NEW PROBLEM: The Gods of Gibberland
Post by towr on Jan 19^th, 2012, 10:13am

Self-referential means that the question refers back to itself, not that it uses iff.