Back to previous post: No fries with that

Go to Making Light's front page.

Forward to next post: Electric Car

Subscribe (via RSS) to this post's comment thread. (What does this mean? Here's a quick introduction.)

This logic puzzle was created by Raymond Smullyan (author of* What Is The Name Of This Book?*) and reprinted here: OpenCourseWare on critical thinking, logic, and creativity:

Three gods A , B , and C are called, in some order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A , B , and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer in their own language, in which the words for yes and no are “da” and “ja”, in some order.You do not know which word means which.

While we’re looking for puzzles, here’s one that requires only elementary geometry to solve:
World’s Hardest Easy Geometry Problem. Find angle *x*.

A sliding-tile puzzle. Move the green block to center-bottom. Who knew that the old Wordstar Diamond was still in play?

This graphic puzzle-game involves code-breaking: Notpron, the hardest riddle available on the Internet

Hm. I'm assuming each question has to be addressed to a single god; that I can't have all three answer and have it count as one question.

And I wonder whether the gods can predict Random's answers. I suppose they have to be able to; if I ask True "Will Random admit to being Random if I ask him if he is?" he either needs to be able to answer Da or Ja, or answer with the equivalent of "I don't know".

Avram @ 1: My assumption was opposite to yours; I assumed each god answers each question. If so, two will always answer in unison, and once I figure out which one is Random I can use its answers to figure out which of the other two is lying and also which word means "yes" and which "no." For my way to be resolved within three questions, though, Random has to be cooperative and show itself on my first question.

**Liza**, I assumed otherwise, because (1) otherwise the puzzle is too easy, and (2) in the ancestor of this puzzle (two figures, one of which answers truly and the other falsely) only one will answer the question.

Nope, each question is posed to an individual god, and the gods cannot predict how Random will answer. It deserves its reputation as a hard question (although I don't think it's the hardest one that Smullyan has devised); as a start, you might prefer assuming that the gods will answer yes or no instead of ja or da.

Hint: Gur xrl vf gb nfx gur svefg dhrfgvba va fhpu n jnl gung lbh xabj bar bs gur tbqf gung vf abg Enaqbz. Gura nfx gur arkg gjb dhrfgvbaf bs gung tbq.

Another addictive time-waster: Fantastic Contraption

Matthew @ 4: Fvapr Enaqbz jvyy nyjnlf tvir rvgure gur fnzr nafjre gung Gehr jbhyq be gur fnzr nafjre gung Snyfr jbhyq, ubj qb lbh cebcbfr gb gryy jvguva bar dhrfgvba juvpu tbq vf Enaqbz?

Liza @ 6: Lbh pna'g. Ohg lbh qba'g arrq gb anvy qbja gur Enaqbz tbq va gur svefg dhrfgvba. Nyy lbh arrq vf gb svaq n tbq gung vf qrsvavgryl qrgrezvavfgvp. Fcrpvsvpnyyl, lbh pna nfx n dhrfgvba bs N jvgu gur cebcregl gung vs fur nafjref bar jnl gura lbh xabj gung O vf abg Enaqbz naq vs fur nafjref gur bgure jnl gura lbh xabj gung P vf abg Enaqbz.

I spent several hours working on this once. Never solved it, though I worked out a number of implications. (Of course, this doesn't indicate much beyond the fact that I'm not especially good at logic puzzles.)

Matthew @7: Ohg lbh pna bayl xabj gung vs lbh xabj juvpu nafjre zrnaf lrf naq juvpu zrnaf ab, pna'g lbh? Jvgubhg gung vasbezngvba, gur npghny nafjre gb gur svefg dhrfgvba vf zrnavatyrff.

Abj, V unir n *cnve* bs dhrfgvbaf gung pna va 2/3 bs cbffvoyr fvghngvbaf trg zr n aba-Enaqbz tbq gb nfx gur guveq dhrfgvba gb, ohg gung'f abg rabhtu gb fbyir gur ceboyrz, V guvax.

V qba'g guvax V pna vzcebir ba zl svefg dhrfgvba, ohg gurer znl or n orggre jnl bs pubbfvat jub gb nfx gur frpbaq bar guna whfg nfxvat n qvssrerag enaqbz (ohg abg arprfnevyl Enaqbz) tbq.

(Warning: potentially more in depth spoilers than the previous ROT13 comments contained in this one. I don't think the ROT13 question here is useful, but you may want to avoid reading it just in case...)

I can easily do it with 4 questions, BTW. The question "vf gur nafjre lbh'er tbvat gb tvir zr gb guvf dhrfgvba gehr?" vf nyjnlf nafjrerq ol nyy tbqf jvgu gur jbeq sbe lrf, which enables me to take the strategy that Matthew's talking about.

The big complication is Random. It's easy to construct a question which both True and False will answer the same way, allowing you to translate to Yes and No, and half the time that will also tell you who Random is. But half the time Random will give the same answer as the other two.

My brain hurts.

Jules @11 & Dave @12: How about something like this (I'm in a rush to do something, so I haven't thought it through very carefully):

Va gur fgnaqneq gjb-tbq Gehr/Snyfr ceboyrz, lbh hfhnyyl nfx rnpu tbq jung gur bgure bar jbhyq fnl. Fb ubj nobhg lbh nfx rnpu tbq jurgure gur bar gb vgf evtug (fb gb fcrnx) jbhyq nafjre enaqbzyl? Npghnyyl, gung jba'g dhvgr jbex. Ubj nobhg nfxvat nyy guerr bs gurz nobhg bar cnegvphyne tbq? Be fbzrguvat yvxr gung?

Dave Bell @12,

I believe the random god will always give you the same answer as the other two, not just half the time - I think the rule that "whether Random speaks truly or falsely is a completely random matter" means just what it says, that Random will answer as if she were either True or False, not that Random will give answers that have nothing to do with the question.

I'm pretty sure questions 2 and 3 were both in Professor Layton and the Curious Village.

(I am so hoping the sequels get translated. Logic puzzles in a steampunk scifi plot with a Miyazaki-esque art style made for a very pleasant rainy afternoon.)

I haven't read the other ROT13'd comments yet, but here is a (fairly major) hint on the first puzzle:

Pbafvqre gur dhrfgvba: "Vs V nfxrq lbh K, jbhyq lbh ercyl wn?" Guvf dhrfgvba, jura nfxrq bs rvgure n gehgu-gryyre be n yvne, jvyy cebqhpr gur nafjre "wn" vs gur nafjre gb K vf "lrf" naq "qn" vs gur nafjre gb K vf "ab". Ol senzvat nyy lbhe dhrfgvba va guvf sbez, lbh ner erqhprq gb gur rnfvre ceboyrz bs gjb gehgu-gryyref naq bar enaqbzvmre, nyy bs jubz nafjre va Ratyvfu.

I adore Raymond Smullyan. He's the master of Knight/Knave puzzles and variants thereof. Alice in Puzzle Land was, in many ways, my gateway drug into the world of logic puzzles, although the more advanced liar/truthteller concepts (like the one cited above, or the sane/insane vampires in WitNotB) are the ones that really blow me away.

Incidentally, Haley, in Order of the Stick, came up with a great solution to many Knight/Knave puzzles (not counting ones like the one Jim cites above, or any other puzzle that doesn't have the knights/knaves speaking English).

As to other time-wasters, I spent way too much time this week playing splitter, a puzzle game in which you have to cut ropes and wooden blocks to move items.

Re: the missing information, i.e. may the questions be addressed to the group with an answer forthcoming from each god? or, must each question be addressed to a single god with an answer from only the god to which it was addressed?

Has a solution been found to the latter case?

Sadly, nearly all of Smullyan's work is out of print, but he has some real gems. For me, the real masterworks are later in his books when he leaves the Islands behind and takes the reader on a tour of combinatorial algebra (in "To Mock a Mockingbird" or "Satan, Cantor, and Infinity") or modal logic (in "Forever Undecided"). But it all winds up being relatively accessible.

Just for lulz, here is a Full Monty solution. Here there be spoilers. First, the easier problem where the gods answer yes/no:

Gurer ner frireny cbffvovyvgvrf sbe gur svefg dhrfgvba, juvpu lbh fubhyq nfx bs N. Urer ner n srj jvgu avpr jbeqvatf gung lbhe nirentr tbq jbhyqa'g dhvooyr jvgu:

* Ubj jbhyq lbh erfcbaq vs V jrer gb nfx lbh "Vf O Enaqbz?"

* Vf O "zber yvxryl" gb gryy gur gehgu guna P?

Sbe rvgure bs gurfr dhrfgvbaf, nffhzr N nafjref lrf. Vs N vf abg Enaqbz, gura lbh pna fubj gung O vf Enaqbz. Va bgure jbeqf, vs N nafjref lrf gura rvgure N be O vf Enaqbz. Lbh pna fvzvyneyl frr gung vs N nafjref ab gura rvgure N be P vf Enaqbz. Ohg gur vzcbegnag cneg vf gung rira gubhtu lbh qba'g xabj jub vf Enaqbz, lbh xabj fbzrbar jub qrsvavgryl vfa'g. Gur bgure gjb dhrfgvbaf tb gb gung crefba, naq lbh pna frr gung "Vf gjb cyhf gjb rdhny gb sbhe?" naq "Vf N Enaqbz?" jvyy tvir lbh rabhtu vasbezngvba gb gbgnyyl fbeg bhg gur vqragvgl bs nyy guerr.

and to adapt it to the ja/da problem at hand:

Sbe rnpu bs gur dhrfgvbaf D va gur cerprqvat fbyhgvba, nfx "Vs V jrer gb nfx lbh D, jbhyq lbhe erfcbafr or qn?" Vs gur tbq nafjref qn, gura gur tbq jbhyq unir nafjrerq lrf gb D vs fur fcbxr Ratyvfu, naq fvzvyneyl wn zrnaf ab. Nzhfvatyl, nsgre fbyivat gur ceboyrz va guerr dhrfgvbaf lbh fgvyy qba'g xabj ubj gur erfcbafrf genafyngr vagb Ratyvfu.

I'm no longer particularly good at those story-type logic puzzles. I keep wanting to push the boundaries of the story. Faced with the three gods puzzle, my first thought was "Don't these gods have worshippers? Probably they know which is which. I'll just Google them and see if they've got a website..."

The internet time-waster I've been using lately is Kingdom of Loathing. Luckily there's a built-in limit to the amount of time you can waste on it per day.

Wesley (#21) True, but there are a number of ways to increase the KOL turn limit. And even once you've exhausted that, there are the games in chat, etc.

20: *Nzhfvatyl, nsgre fbyivat gur ceboyrz va guerr dhrfgvbaf lbh fgvyy qba'g xabj ubj gur erfcbafrf genafyngr vagb Ratyvfu.*

Vg frrzf jbegu cbvagvat bhg rkcyvpvgyl gung guvf jvyy or gehr bs nal fbyhgvba gb gur chmmyr: gurer ner fvk cbffvoyr pbasvthengvbaf bs tbq, gjb cbffvoyr genafyngvbaf bs gur ynathntr, naq ab jnl gb qvfgvathvfu orgjrra gjryir qvssrerag cbffvovyvgvrf jvgu bayl guerr lrf-be-ab dhrfgvbaf (hayrff lbh purng).

(rot13'd because, while it doesn't contain a solution, it contains the realization that put me on the path to a solution)

Claim: ng yrnfg bar bs gur dhrfgvbaf zhfg vaibyir gur jbeq "qn" be "wn".

Proof: Vs gurl qvqa'g, gura gurer jbhyq or bayl 4 cbffvovyvgvrf (fvapr punatvat gur genafyngvba jbhyq or cbffvoyr), naq gurer ner 6 nafjref gb pubbfr nzbat.

That's what comes from doing too much work on resolution proofs: assume the opposite (impossibility), try to prove it, and see where the unprovable lemma (or the hole in the proof) is.

Avram @1: The OpenCourseware site that Jim pointed to states "each question must be put to exactly one god," but Jim did not copy that when he reproduced it here. I would assume it still applies.

#25: *but Jim did not copy that when he reproduced it here.*

I have no idea how that got dropped. The semicolon separating the two parts of the sentence came through fine and it was meant to be a straight cut-n-paste.

I've now corrected the problem.

Imagine being a 911 operator in the Village Where People Only Tell Lies. People would keep calling you up and saying they were fine.

(I wrote a story about that once)

I have an old wooden version of that sliding puzzle. I think it belonged to my uncle who died in the 1940s. It's called "Dad's Puzzle." ("Few can solve it! It can be solved!")

Adam @22, *ahem*, I think that might be what's called 'enabling'.

(Gleaned from usage: handing a glass of booze to an alcoholic. Official meaning may differ.)

Note to Self: Never follow those links. (Probably shouldn't read the posts.)

The sliding puzzle is known as the parking garage or bus puzzle here (we had a wooden one too).

Chris @14: *I think the rule that "whether Random speaks truly or falsely is a completely random matter" means just what it says, that Random will answer as if she were either True or False, *

Chris, as far as I can see, that's *not* what that rule says. Answering "truly" is not the same as "answering as if you were the one named 'True'", and answering "wrongly" is not the same as "answering as if you were the one named 'Wrong'". As far as I can see, if you ask Random "Are you True", then she will either truly answer "No" (well, in the gods' language), or falsely answer "Yes", while, if she would always answer *as if she were either True or False*, she would always answer "Yes".

Or am I wrong here?

(Sorry if someone sees my previous post as a spoiler- I think it isn't, because it's a question about what the conditions of the riddle are.)

I notice that on the page with the geometry problem, there's a second, similar problem with the base angles slightly larger. The notes say that you don't solve that one the same way.

My feeling is that it ought to be possible to solve the general problem, and derive a formula for angle "x" based on any values of the four angles down at the base. I've looked at that a little, but not gotten much done so far.

#33 *My feeling is that it ought to be possible to solve the general problem*

Yes, and the general solution is "use trigonometry."

The Law of Sines makes solving this one a snap. The trick comes in solving it using a straightedge and the knowledge that the interior angles of a triangle add up to 180.

The first step in solving the triangle problem:

Qenj n yvar guebhtu cbvag Q cnenyyry gb NO.

A question on the geometry puzzle--if it's a spoiler, please delete it.

Does it have a definite answer, or a family of answers? I think I have two fully consistent solutions which aren't the same.

*Does it have a definite answer, or a family of answers?*

I don't know the official answer to the problem.

I've found the same answer two different ways, if that helps. That doesn't rule out some other, but it's good enough for me.

Oh -- the actual first step in the triangle problem: Any time (and I mean *any* time--on the SATs or wherever) you see a geometry problem with a diagram labeled "Not drawn to scale" your *first* bleeding step is to draw the bleeding thing to scale.

#38

Used CAD system. Then measured the angle. Much easier than trying to get there by logic ....

Yeah, I mean, he says (if you follow the "very small hint" link on the site) that you should use a protractor and draw the damn thing to scale.

I would think it would be very hard not to glimpse X when you're drawing it.

#40, Falconer -

Wouldn't that be measuring the angle instead of solving for it? You can print the diagram he provides to avoid getting spoiled instead. And I must say, I'm kinda startled by the idea that the accuracy of the diagram matters. My geometry class back in the mists of time didn't allow for any assumptions that an accurate diagram would make or break. You don't look at something and decide that it is parallel or congruent, you prove so, or are provided that info. Otherwise, it ain't so.

The geometry problem is the one I latched on to, and I'm utterly stumped at the moment. I'm pretty discouraged by logic puzzles most of the time because I don't seem to do well enough at them to get any better, so I have to resort to using hints and cheats. When I'm not using the hints and cheats (and sometimes even when I am), then I end up giving up for lack of progress. I don't seem to ever get better. *sigh*

The penultimate level of fantasticcontraption took me forever. Yeesh. I'm relatively pleased that my solution does have fewer parts than most of the others that were posted on that site's discussion forum, though-- elaborately multilinked chains are neat, but I just don't have the patience to make those things.

First geometry problem seems to boil down to finding the angles created by a diagonal running from the 140 to the 150 degree vertices of a 50-140-20-150 irregular quadrilateral. By drawing the other diagonal and dropping lines from the vertices to meet the new diagonal at right angles, then drawing a rectangle around the points defined by vertices and parallel to the new diagonal, I end up with a system of simultaneous equations that I should be able to solve! Dammit!

Can I have a ruling from someone who knows the answer whether Chris @ 14 or Raphael @ 31 is right?

Also, Fantastic Contraption rocks my socks. These are my two favorites from my solutions:

Chaingang: Beautiful in its hideousness

Friends: It just gives me that warm fuzzy feeling

And I like Alley Oop for being so contrary. Okay, my favorite three.

(I like Hook too. I'll stop now, I promise.)

#44 *Can I have a ruling from someone who knows the answer whether Chris @ 14 or Raphael @ 31 is right?*

I consider that when you ask Random a question, he turns her back, flips a god-coin, and depending on whether the coin comes up "da" or "ja" tells the truth or doesn't.

I do believe x=guvegl.

Now that I've remembered about parallel lines...

Argh. Geometry.

V znqr n zvfgnxr ba gur zngu, naq vg pnzr bhg evtug naljnl orpnhfr OQR naq NRQ ner rdhny natyrf.

Now I need to PROVE it.

... rot13 may not be strong enough of a cypher.

heresiarch @44: *Can I have a ruling from someone who knows the answer whether Chris @ 14 or Raphael @ 31 is right?*

I would suggest that the answer is Mu. In theory, there are questions where the distinction is important. For instance, any god who is capable of answering "Are you going to answer (your language's word for) 'no' to this question?" is Random and not bound to lie or tell the truth. But here you should assume that "yes-no question" means a question that any god *can* answer with (their word for) yes or no. A similar non-issue would be whether False lies out of delusion or contrariness (and, hence, whether his beliefs are correct even if his statements are not).

And wow. I like playing Fantastic Contraption this much. But I like watching other people's fun designs THIS much!

Matthew Daly@48:

No Mu for you! "Are you going to answer 'no' to this question?" is an easy question for False: he can say "yes" (lying) or say "no" (still lying). However, True would have a seizure, or hit you with lightning, or something.

Now, I think this discussion has attributed *three* possible definitions for Random. This is compounding the confusion. Let us imagine three different aspects of the Random god. (I am ignoring the language issue, obviously.)

Random-Answer: Flips a coin when asked a question. Heads: say "yes"; tails: say "no".

Random-Valence: Flips a coin when asked a question. Heads: give the answer which is true; tails: give the answer which is false. (This is what Jim@45 describes.)

Random-Copycat: Flips a coin when asked a question. Heads: give the answer which True would give if asked that question. Tails: give the answer which False would give if asked that question.

Note that Random-Answer is the only one who is really ignoring the question.

Also note that you can invent three *more* aspects -- same as the above, except they flip their coin once per *questioner*, or once per conversation, or once per lifetime -- not once per question. (Was this what Chris@14 meant by "not just half the time"? I'm not sure.) However, once-per-question is the traditional model for these puzzles.

Now, none of these is a "Mu" distinction. I'm pretty sure you can tell them all apart by asking the right questions. (Sorry, I'm not actually great at these puzzles.)

The question of delusion versus contrariness isn't all that "mu" either. It's perfectly possible to turn to False (once located) and ask him, "Do you *believe* that two is an even number?" If False is sane and lying out of contrariness, he will say "no". If he lies because all his beliefs are false, he will say "yes" (in fact he doesn't, but he is deluded about that fact!) There's a whole set of puzzles based on this distinction. (You also have the god who is deluded *and* contrary, so he accidentally answers all questions with the truth...)

(Although the puzzle setup doesn't have to support this stuff. The writer could declare that gods are miserably unintrospective, and really don't think about their own beliefs, in which case these questions fall into the "I don't know" bucket.)

David Goldfarb @ 33: The give-away against the "general case" is that he's giving you actual angle sizes. This particular setup has a bunch of nice properties to exploit: BDC is isosceles, and a simple construction gives you an isosceles triangle based on AC as well. Which makes for a bunch of interesting observations on how special certain intersections are in this diagram.

I can write a system of equations for 4 unknowns which I think should give me x; does this work for anyone else? It seems to make the problem rather trivial. Or are the equations degenerate? Back to the drawing board...

#51, Jakob --

I got to that eventually but haven't had the time to poke at it with my decaying algebra and get anything resembling a correct answer. (I'm relatively certain X =/= 0, which is what I got on my first pass through.) I'm not at all certain that it is a workable solution, but it is one I haven't given up on yet.

(Oh, hey, I just remembered that vs lbh fhogenpg n ynetr natyr sebz n fznyy bar, lbh qb trg n erny aba-artngvir ahzore - vg jencf onpx cnfg guerr uhaqerq naq fvkgl. Gung znl znxr n qvssrerapr! (Math is not one of my native skills, as you can see.)

Delurking to say that I am now totally hooked on notpron. And look to be for the indefinite future. Thanks, I think.

*Who knew that the old Wordstar Diamond was still in play? *

WASD is a fairly standard alternative-cursor-keys layout, used amongst others by multi-person games and an awful lot of first-person shooter fans.

Okay, I finally managed to find a general equation for the angle *x*, in terms of base angles a, b, c, and d -- that's reading left-to-right, so that in the diagram above a=10, b=70, c=20, and d=60. I used the Law of Sines, arbitrarily assigning the base of the triangle a length of 1. (Although if my logic is correct, that length drops out in the derivation -- as indeed it should.)

It was a lot harder than I expected to get an equation with x on only one side, and the formula came out a lot hairier than I thought it was going to.

Here it is:

tan x = sin a * sin c * sin (b+c+d) / ((sin (a+b+c) * sin (c+d)) - (cos a * sin c * sin (b+c+d)))

I put a few extra parentheses than strictly necessary in the denominator there, I hope they make it easier to read.

I checked the formula for the case we're given here. It was very exciting when I finally hit the "arctan" button on my calculator and the number 20 popped out.

Good lord, the lengths you're all going to to solve this triangle problem. All I can say is "yur doin' it wrong."

The only thing you need to know to solve it is that the three angles of a triangle add to 180 degrees. Then start working out the unlabeled angles on some of the many nested triangles and you'll have it in no time. I think I'd worked it out in my head in under a minute the first time I looked at it.

... and now having said that, I know what the answer is and I'm sure it's correct, but I can not figure out how I got there. Huh.

Clifton Royston@56: I'm afraid that you are wrong. It is *not* possible to solve the problem purely by filling in angles that sum to 180 or 360. If it were, it would hardly be up there as "The World's Hardest Easy Geometry Problem", now would it? At a minimum you need to draw some new lines in the interior, and use reasoning that involves similarity and congruence.

Plus that doesn't solve the general case, which is what I was interested in.

Whoops! I just looked at the equation I posted, again, and while the equation is right, and my explanation of the notation is correct, the example I give is wrong -- it should be "c = 60, and d = 20", not the other way around.

Talking of time-wasters, I wonder if the people here (I'm thinking especially of Avram) know that there's now an online server for the card game Dominion? It includes all existing expansions, including the new "Prosperity". You can customize your card set to a great degree, although I for one usually just have it choose randomly from all of them.

Here's a new one that I'm surprised nobody did earlier:

TetriSweeper! Half the board starts out as a Minesweeper game, and while you're playing that, tetrominoes drop down from the sky. A tetromino that lands gets added to the Minesweeper playing area. A row disappears if it's completely full *and has been fully swept for mines*. Game over if you hit a mine *or* the row stack hits the top. It's the Reese's Peanut Butter Cup of PC games.

Kingdom Rush -- on the Kongregate site -- is very engrossing, but has a set number of levels to plow through.

David Goldfarb @ #61:

That's some powerful timewaster, right there.

I could sworn I had an evening around here somewhere...

And the lack of coherency just screams potted meat product.

I solved the slider puzzle, which is gratifying, as I have had a wooden version of it that probably belonged to my grandfather or uncle (the box calls it "Dad's Puzzle," but I'm pretty sure it wasn't his). The website didn't keep track of my time, and neither did I, but since I never managed to finish it before, it was still kind of nice.

Dire legal notice

Making Light copyright 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014 by Patrick & Teresa Nielsen Hayden. All rights reserved.

Internet Time-wasters III: