Brain teaser

[nelg]

So you're wrong nelg. Stans chance of being executed is 2/3 just like Joe said. The thread I linked to has elaborate explanations of all this. The really funny part is that the probability that Eric gets killed is 1/3, so Stan would be better off "switching places" with him if it was possible.

O.K. I will try this sans caffeine. If two out of three are going to die, then in any group of two at least 1 will die. If there is no information, with regards to Erics status, from the guard then the only new information that Stan receives is that Kenny will certainly die. With the certainty out of the way all we know is that one of two remaining will die giving a probability of ½ for either Stan or Eric.

 

[Humus]

Similar to the one by GameCat.

You are a prisoner being given one last chance for freedom. The guard show you three doors where two leads to the execution chamber and one to freedom.

You get to pick a door.

After the choice is made one of the remaining doors are opened and shown to have led to your death.

You now get the opportunity to alter your choice.

What do you do, and why?

You change to the other unopened door. This will improve your chances from 1/3 to 2/3.

 

[Zaphod]

Try this one:

Gilgameshl invades a village of smurfs and announces that he's going to kill and any who don't pass his test. He says he will return the next day, line all of the smurfs up single file (there are 100 smurfs) and put hats of either red or blue on each of them. Each smurf in turn must call out "red" or "blue" and any smurf who does not call his own hat color correctly gets
killed.

Think I got it.

The odds are even for saving all of them, and for saving all but one.

 

[Snyder]

Stan puzzle

And please play nicely, the last time I posted this people became really angry and upset with me and I had to spend a lot of time explaining probability theory.

What do you expect when even mathematicians have flamed one another to death over this problem in the past?

 

[Xmas]

Think I got it.

The odds are even for saving all of them, and for saving all but one.

Right. Their plan is that the first one says blue if the number of blue hats he is seeing is odd, so everyone else can tell the color of their hats out of the number of blue hats they see and the information given by their predecessors.
if (times blue has been said + number of blue hats visible) % 2 == 1
say blue
else
say red

 

[Simon F]

Of course, you've probably all heard of the other prison which has two doors - one to freedom and the other to an excruciating death. There are two guards and the prison warden tells you that one always lies while the other always tells the truth. You are allowed to ask one question to one guard. What question would you ask?

As a slight variant, just after you ask the question, the warden tells you that he was joking. Actually, they both either lie or both tell the truth. What do you do?


A slightly more difficult version that I've just thought of is that the Warden initially tells you that there are 3 possibilities

• The both always tell the trurh
• They both always lie OR
• There is one liar and one truthful guard

What question would you then ask?

1) if the memory is empty, and you want to store I, write a '1' into bit position I. To read back, if memory contains only 1 bit, then that bit position represents the integer we stored.

2) if the memory contains 1 bit, and is in state I, and you want to write J, then store '1' in position K where {I,J,K} are on a line in the Fano plane. (see picture).

That definitely does not work. I don't yet know if the puzzle is impossible (as you have stated it) but that proof certainly is incorrect.

Storing a first number in the range [0..7] using a single bit works because you can assume the initial "all zero" state is zero, thus you only ever need to write values in the range 1...7.

You can't then store the next value with only one more bit. Let's assume you've initially stored M (from [1...7]) and now wish to store N belonging to the range [0..7]. We can ignore N==M since there's no need to write that. There are 7 such choices BUT there are only 6 unwritten bits. You therefore need more than one bit to encode the new value.

 

[DemoCoder]

That definitely does not work. I don't yet know if the puzzle is impossible (as you have stated it) but that proof certainly is incorrect.

Storing a first number in the range [0..7] using a single bit works because you can assume the initial "all zero" state is zero, thus you only ever need to write values in the range 1...7.

The problem as stated is to store 1 through 7, not 0 through 7. Go back and look at my original specification. I just silently switched the range to 0 to 6 when I discussed the solution.

Edit: opps, I just looked at it, I did say 0..7 in the original description of the puzzle. Opps, I guess we are 1 for 1 on posting puzzles with bugs in them.

Of course, you can only store 1-7 or 0-6 because the Fano plane only has 7 points (not 8)

 

[Basic]

You change to the other unopened door. This will improve your chances from 1/3 to 2/3.

No it doesn't improve your chances quite that much. Only to 50:50 I'm afraid. So guys, don't land yourself in that sort of prison!

Hey Simon, I'm a bit dissapointed that you'd fall for that. The question is isomorphic to GameCat's, except for the ability to do the choice in the end.
You agreed that Stan had 1/3 chance to live (with the reformulation). That's equivalent to the prisoner's situation if he can't change his choice.
And since one door that lead to death is known, the remaining 2/3 chance to life must be behind the other door.

 

[Simon F]

Hey Simon, I'm a bit dissapointed that you'd fall for that. The question is isomorphic to GameCat's, except for the ability to do the choice in the end.
You agreed that Stan had 1/3 chance to live (with the reformulation). That's equivalent to the prisoner's situation if he can't change his choice.
And since one door that lead to death is known, the remaining 2/3 chance to life must be behind the other door.

The sad thing is, I knew that. Serves me right answering before getting my first coffee.

 

[Basic]

And there's a very simple solution to the constantly lying/truthful guards. But I've never seen anybody claim it to be the right answer. It even works if there's just one guard, but he's known to always be lying/truthful.

"What would you answer if I asked you what door goes to freedom?"

Note that you get a double negation from the double question.

 

[Simon F]

And there's a very simple solution to the constantly lying/truthful guards. But I've never seen anybody claim it to be the right answer.

Ok I've changed the wording slightly.

"What would you answer if I asked you what door goes to freedom?"

Note that you get a double negation from the double question.

It's just that that might be construed as ambiguous in English so I think it's safer to phrase it as "What would your colleague answer if ..." (and then take the other door). Now, if we could ask him in "C" then I'd have no problem with it

 

[Basic]

Oh why can't we get a nice unambigous language. And preferably with some elegant way to avoid referencing errors (local variables?).
German could of course get one cool-point for it's stack-based nature.

About the fano planes:
I would use a different numbering. If you start with 1,2,4 in the corners of the outer triangle, and name the other nodes as XOR of two other nodes in line with it, you'll get an easy way to calc "the third point in line". (This assumes a numbering 1..7).

You also get a nice way to calc the coded number. XOR the bit number of all set bits in the codeword. This will work for any number of bits set.

 

[thana]

sorry for bringing up this old topic again, but i just read it and some things are not quite clear to me:

The ceiling is 50 metres off the floor, the walls and ceiling of the tower are perfectly smooth, and the ropes are 1 metre apart. The ropes hang vertically and reach all the way to the floor. The thief is an expert at rope climbing etc, can safely land after a fall of 3 metres, and is equiped only with a knife.

Approximately how much rope can he steal?

Depending on how well he can make knots while rope climbing, approx. 98m

He can probably do slightly better (say 98.5) but that's pretty close.

why 98.5m and not close to 100m?

the way i see it, he can cut off the first rope directly at the top while hanging at second, then knotting the just-cutted-off rope directly at the top onto the second one (with a detachable knot, like on your bootlaces), then cutting the second rope directly beneath this knot and then knotting it to the knot in a way so that you can open the knot by pulling the second rope. finally he slips all the way down (on the first rope), pulls the second rope and now both ropes fall to the ground!

the only limiting factor would be the thickness of the ropes. if the ropes where made from one thin string of nylon, the maxium length could probably be something like 99.99m

A slightly more difficult version that I've just thought of is that the Warden initially tells you that there are 3 possibilities

• The both always tell the trurh
• They both always lie OR
• There is one liar and one truthful guard

What question would you then ask?

i can't think of a question which would give you the right answer in all possibilitys. neither the double negation nor the "what would your colleague say" question would be sufficient alone, unless you consider chaining the two questions together in one sentence as 'one' question.
so how is the question supposed to look

Oh why can't we get a nice unambigous language. And preferably with some elegant way to avoid referencing errors (local variables?).

there are indeed some artificial languages which are completly based on the rules of logic, the most well-known and the one with the greatest vocabulary is certainly "lojban" (which itself is derived from "loglan", the logical language). i once tried to learn it by myself with the lessions from their website (www.lojban.org), and it stunned me how fast i was able to get the meaning of the words and the grammar. with this language its impossible to understand someone in the wrong way from what he has said or written. i guess this could be especially helpful to prevent some flamewars that originate from misunderstandings

EDIT: typos

 

[Simon F]

sorry for bringing up this old topic again, but i just read it and some things are not quite clear to me:

The ceiling is 50 metres off the floor, the walls and ceiling of the tower are perfectly smooth, and the ropes are 1 metre apart. The ropes hang vertically and reach all the way to the floor. The thief is an expert at rope climbing etc, can safely land after a fall of 3 metres, and is equiped only with a knife.

Approximately how much rope can he steal?

Depending on how well he can make knots while rope climbing, approx. 98m

He can probably do slightly better (say 98.5) but that's pretty close.

why 98.5m and not close to 100m?

the way i see it, he can cut off the first rope directly at the top while hanging at second, then knotting the just-cutted-off rope directly at the top onto the second one (with a detachable knot, like on your bootlaces), then cutting the second rope directly beneath this knot and then knotting it to the knot in a way so that you can open the knot by pulling the second rope. finally he slips all the way down (on the first rope), pulls the second rope and now both ropes fall to the ground!

the only limiting factor would be the thickness of the ropes. if the ropes where made from one thin string of nylon, the maxium length could probably be something like 99.99m

Did I say 98.5? Sorry I meant ~99.5

That's a sligtly different solution (sounds a bit risky though) to the one I had in mind but my assumption was that, because the ropes are 1m apart, he can't easily reach right across the whole gap and support his weight at the same time.


My solution was for the thief to initially tie the bottoms of the two ropes together. Climb up the two ropes but cut one about 50cm below the ceiling (and hang on to (or tie to his waist) the end that would otherwise fall). Tie a loop in the 50cm bit (which he should still be able to reach from his rope). Thread the other cut end he was holding on to through the loop and then transfer his weight on to the "doubled up" rope. Finally cut the other end right off at ceiling and lower himself down using the doubled ropes.

A slightly more difficult version that I've just thought of is that the Warden initially tells you that there are 3 possibilities

• The both always tell the trurh
• They both always lie OR
• There is one liar and one truthful guard

What question would you then ask?

i can't think of a question which would give you the right answer in all possibilitys. neither the double negation nor the "what would your colleague say" question would be sufficient alone, unless you consider chaining the two questions together in one sentence as 'one' question.
so how is the question supposed to look

I've forgotten how I worded it now but it relied on double negatives. Something like "If someone else were to ask... what would you have told them".. In fact, you only need one guard.

Oh why can't we get a nice unambigous language. And preferably with some elegant way to avoid referencing errors (local variables?).

there are indeed some artificial languages which are completly based on the rules of logic, the most well-known and the one with the greatest vocabulary is certainly "lojban" (which itself is derived from "loglan", the logical language). i once tried to learn it by myself with the lessions from their website (www.lojban.org), and it stunned me how fast i was able to get the meaning of the words and the grammar. with this language its impossible to understand someone in the wrong way from what he has said or written. i guess this could be especially helpful to prevent some flamewars that originate from misunderstandings

I'm sure Goedel could find a flaw in it