jack

Yeah :) Although that's not really a logic puzzle. Not getting stabbed is some sort of dexterity/tact test... :)

From:

This is very cool. I'm working on it.

I've seen it in three places in the last hour (clearly not coincidentally) (here,

andrewducker, and an email from

robhu to me and

alextfish) so I'm not sure which of those to discuss it in.

I think the puzzle is a bit underspecified. Are questions of the form "would your neighbour say yes if I asked him blah?" disallowed, because the correct answer might be "I don't know" if the neighbour is Random? Or can True and False see the future and predict (truthfully and falsely, respectively) what Random will say, and then Random has to abide by that if asked? Secondly, are you allowed to mention "da" and "ja" in your questions? I assume "Say da if 2+2=4" is disallowed, because it feels like cheating and isn't strictly "a yes-no question"; but what about something like "Is it possible for your neighbour to say da to question X?"

I shall continue to think about this one (at the expense of work, no doubt :/ )

From:

robhu.livejournal.com

Due to my LJ omnipresence you can discuss it anywhere you like and I'll see it ;-)

From:

That was one of my reasons for choosing here to discuss it.

From:

I saw it here: http://nielsenhayden.com/makinglight/archives/010782.html#010782, and expect the other references came from there. My recitation of it was extremely underspecified, just enough to specify exactly which puzzle it was, but not enough to helpfully explain what's going on to anyone who hasn't seen it before. I think that version is complete enough to make sense.

My reading is that:

* Paradoxes, "I don't know", and so on don't happen: it's possible to solve the puzzle without them, and not specified what happens if they come up
* Although other puzzles may answer it differently, random may answer in the least helpful way possible, and the other gods don't know in advance what s/he's going to say.
* You can't say "say blah if..." as that breaks the "respond yes-or-no", but you can ask questions like "does da mean yes" and "will God 3 answer ja if I ask..."

Without wanting to give answers away, if you're intrigued, I'd suggest first considering which of precursor puzzles you've seen before. I assume you've seen the two-guards-two-doors-one-yes-no-question puzzle, and may have seen similar Smullyan problems introducing the strange language idea (you meet a guard of two door who answers da-ya to one true-false question, etc):

* The three gods problem, but the Gods answer in English. This is hard enough, I remember being stuck the first time I heard it.
* The two-guards-two-doors problem, but with the gods answering in da-ya.

From:

Sorry, I didn't mean your version was underspecified; obviously your version was a quick summarised reference to it. I meant this statement of it, which is the one Andrew and Rob linked, and seems to be worded the same as the one you just linked.

I assume you've seen the two-guards-two-doors-one-yes-no-question puzzle
Yes.

may have seen similar Smullyan problems introducing the strange language idea (you meet a guard of two door who answers da-ya to one true-false question, etc)
Not that I recall.
You said up-thread that the language was irrelevant, so I'm trying to think of a solution without it, and then I'll see if it generalises easily to the case with it.

From:

may have seen similar Smullyan problems introducing the strange language idea (you meet a guard of two door who answers da-ya to one true-false question, etc)
Not that I recall.
OK, got that one now...

The two-guards-two-doors problem, but with the gods answering in da-ya.
And that one.

It's the randomness that's throwing me.

From:

Yeah, that's the really interesting wrinkle, it definitely threw me. You really can't get any information out of the random God's answers.

From:

Indeed. He's equivalent to a coin toss.

From:

Yeah, although potentially even worse than that. If you have lots of questions, you can easily identify a coin-toss god by asking the same Q repeatedly. But if how "random" works isn't specified, it might even be "answers as if s/he were the truthful god and the truthful god were the random god" or something. If you've only got three questions, that's not any worse, but thinking that the random answers may be those is a helpful way to think about it.

From:

but thinking that the random answers may be those is a helpful way to think about it.
Is it? I don't see how. Surely the most helpful way to think of it is as meaningless. A coin, too, might "answer as if it were the truthful god and the truthful god were the random god" over three flips.

I think I've solved it now, anyway, assuming I'm allowed to change subsequent questions based on previous questions, rather than having to decide all my questions and questionees at the start. It's displeasingly inelegant, though; it'd take a paragraph to write out.

From:

Is it? I don't see how. Surely the most helpful way to think of it is as meaningless.

Well, it ought to be. But my brain keeps trying to interpret random in useful ways, whereas knows to steer clear of actively malicious, so pretending it's malicious is a necessary step to get the intuition vaguely right; if you don't, so much the better :)

I think I've solved it now, anyway, assuming I'm allowed to change subsequent questions based on previous questions

Oh yeah, that didn't come up before, but I assumed so -- I think it's necessary, and indeed deciding you need to work out who to ask is one of the first things you have to do.

Probably so. What was your strategy? It's probably easier to describe that than to try to give a table of questions. My answer was very much (1) tack on 'xor da means yes' to the end of every answer (2) tack on 'xor you are the god that lies' to the end of every answer, etc.

From:

It looks like my answer didn't work after all, as I said elsewhere :(

My strategy involved moving from "what would X say if" (because of the paradox when X is Random) to "what would *you* say if", and noticing that "would you say da if I asked if you were Truth" would distinguish Truth and Falsehood. I thought that if you asked that question to two of them, that would carve up the problem space into three possibilities, each of which had enough information to fully identify all three gods using the remaining question. But now I think I was mistaken for one of the three cases.

Your solution, with its strings of xors, sounds even more inelegant than mine (I mean no offence, since mine doesn't even work). But I was hoping the puzzle would have a nice pretty solution.

From:

Thank you for stealing my evening :-)

I now have a solution - yay! I think it's pretty elegant too and doesn't involve xors. Can I send it to one of you for comparison? I don't want to post it here in case other people are still working on it.

From:

Yay, well done. That makes me more inclined to carry on working on it, knowing that an elegant solution exists.

I'd rather you didn't send it to me yet, since I don't have a working solution after all.

And ... yes, mwahaha, it was an elaborate ploy by me and

cartesiandaemon to steal you away from writing, since your word count is higher than both of ours put together :P

From:

I'd finished writing for the day, anyway. You just prevented me washing up. I'll blame you if pw201 tells me off :-)

I thought of posting the solution under an lj cut in my own journal but wasn't sure if that would hide it for everyone - don't know enough about how people read lj.

From:

PS I did solve the English version first, but didn't think the generalisation was trivial.

From:

I wouldn't want to steal scribb1e from paul, but if that's the game:

http://www.legitgames.com/games/903/shift-3.html
http://www.king.com//game/splitter
http://fantasticcontraption.com/

A christian and a lion are in a circular arena. If the christian can run faster than the lion, can the christian always stay out of reach? If the lion can run faster, can it always catch the christian? What if they can both go at the same speed? [Courtesy of lizzip and Bela Bollobas].

If you have a 6x6 chessboard and tile it with dominos, is it possible to do so so no horizontal or vertical line divides it into two parts without breaking any dominos? [Courtesy of simont]

:)

From:

simont

Courtesy of lizzip and Bela Bollobas

Hee hee. She lent me that book recently. I rather liked "Can every natural number be written as a sum of terms of the form 2ⁱ3^j such that no summand divides any other?".

Courtesy of simont

... though I should warn anyone attempting this problem that I currently don't know of an elegant solution. Though, Jack, can I assume that your posting it here implies that you were convinced by the solution I emailed you last week? :-)

From:

Hee hee

:) Yeah. That book can probably keep someone busy for the rest of their life, given how interesting each individual problem is. (I'm sure I recall Imre giving a talk about the christian and lion problem, or a related one, to trinity maths society.)

can I assume that your posting it here implies that you were convinced by the solution I emailed you last week? :-)

Alas, no. I skimmed through it, and it looked like a plausible case analysis, but I hadn't got round to thinking about it in detail. I nearly warned that there may not be a solution, or may not be an elegant solution but (a) the point was timewasting and (b) I hoped someone else might come up with an elegant/generalisable solution for us :)

From:

Noooo! Free time stolen.

Hey, wait. I think I have an elegant solution to the 6x6 chessboard. Can't see any holes in it right now, so I'll post it to my journal under a cut and you can tell me what I've missed.

From:

Do you two know each other? I can do one of my patented wrong-headed introductions :)

Simon, this is scribb1e, who's very deadly playing board games, married to Paul Wright, has a very nice smile when she's about to do something exciting, is reading through world literature including the bible from the start, and I know via dancing and via alextfish and woodpijn.

Sribb1e, this is Simon, who I know via SGO and the Carlton, an emritus matho (ie. was a mathmo), who is always very friendly and a very good source of interesting maths questions. He wrote PuTTy and "How to report bugs effectively", which includes a nice metaphor about antelope.

From:

Hi Simon! I'm trying to work out if we've met IRL. I was a mathmo too, same year and college as Jacob of PuTTy.

From:

simont

Oops, I've only just noticed this comment (since of course I didn't get a notification email for it, because it wasn't a reply to one of mine). Belated hi to you too! :-)

I don't think we've met IRL, but it's not completely impossible. Since I don't know your RL name or appearance, though, it's hard for me to be sure of that. You have access to both of mine, though, so you're probably in the better position to judge...

From:

Oops, indeed, I'd forgotten that I try to be invisible online. Doh. I thought your face looked familiar and thought we might have met at some point. Er... see this: http://scribb1e.livejournal.com/13683.html

From:

simont

Aha, thank you. Hmm. Your name might conceivably ring a very vague bell, but the face doesn't, so I'm going to have to suppose that we haven't met (unless someone can point out that I've been forgetful).

(Curiously, you're not the first person to ask me whether we've met without giving me enough information to answer. Perhaps in the other case the idea was that if we had met then we'd have done an LJ-names introduction and therefore I'd know...)

From:

Please, let me know. Or post it here -- I doubt anyone is both following the thread and still pondering the puzzle.

From:

I've posted to my LJ under a cut.

From:

Yeah, that sounds like the right ballpark, but not quite working. The analysis I remember was definitely based on carving up the problem space: imagining each answer from a deterministic god gives one bit of information, and you need to distinguish six possible cases.

Your solution, with its strings of xors, sounds even more inelegant than mine

:) Yeah, I pretty happy with it as a way of demonstrating that a solution is easily worked out, I think it's the simple way to understand it, but it doesn't boil down to three simple questions. I seem to recall when the (english) version of the problem was discussed somewhere, I tried to boil it down to something simple, but no-one got anything very elegant. But I may misremember; and Sarah may do.

From:

Ah, I see. The making light one was I think derived from there, but presumably any extra details were filled in by someone pedantic who knew which questions needed answering :)

You said up-thread that the language was irrelevant

That might have been slightly irony -- it's irrelevant to someone who is very familiar with these sorts of problems. But yes, I think the right thing to do is solve that problem first, and then consider the language as a small generalisation to that problem.

I'll refrain from talking about that problem any more, as it's probably more interesting to think about it first before someone tries to give hints, but I can give you some start later on if you like.

From:

That might have been slightly irony -- it's irrelevant to someone who is very familiar with these sorts of problems
Yeah, I thought it was, hence "I'm trying to think of a solution without it, and then I'll see if it generalises easily to the case with it."

From:

...and I've solved the full da/ya version. Yay.

I disagree that it's the hardest one in the world. The hardest one I've encountered is something to do with 100 prisoners opening 100 boxes one at a time in a room, without conferring. I can't remember the precise details, but when I first encountered it it seemed completely out of the realm of possibility, rather than "oo, if I just had one more question / one more weighing / one fewer ball, I could do it". I got the answer eventually, with quite a bit of help, and still find it awe-inspiring.

From:

...and I've solved the full da/ya version. Yay.

Actually I'm not sure if I have, doh. The da/ya version is indeed a trivial generalisation of the English version, but I'm not sure if my solution to the English version was correct after all (or if it was correct and I now can't remember it, which is even more frustrating).

From: