Logic puzzles

[Norinel]

The birthday thread has degenerated into off-topic logic puzzle discussion, so I thought I'd split it off into a new one before things got too out of control. Puzzles from there:

You are in a dungeon and trying to escape. You walk down a hall and come across 2 large and very ugly guards who initially remain silent. Each guard is standing beside a door, so there is a door to the left and a door to the right. The guards are not blocking the doors, just there for decoration it seems, until you notice a sign on the wall:

• The exit to the dungeon is behind one of these doors but which one... Choose correctly and you will win your freedom, choose the wrong one and you will never escape. The guards you see before you are identical twins by the name of Fibkin and Truthkin. Truthkin will always give you the correct answer to your question whereas Fibkin will always give the opposite answer.
  
  You may choose one of the guards and ask him one question.

How can you guarantee your freedom.

In the alternate version, the owner of the labyrinth has made 100 clones each of Truthkin and Fibkin, and two are randomly assigned to guard the exit. In other words, you might be facing 2 Truthkins, 2 Fibkins, or a Truthkin and a Fibkin. How can you figure out the correct door? In this situation, you are allowed to ask one of the guards two yes/no questions.

There are ten people, nine liars and one truth-teller. (The liars know who the truth-teller is) Given three yes or no questions, each directed at one particular person (But it doesn't have to be the same one for all three), come up with an infallible method for finding the truth-teller.

Cheating wives

In a city of the Sultan there was a problem. There were 40 wives in the city who were cheating their husbands. And everyone in the city knew which wife, only the husbands didn’t know that their wife was cheating. The Sultan decided to do something about it.
He wrote out a proclamation which said that all husbands of the cheating wives may kill their wives in the night, but only if they’re sure of it. It didn’t how many wives, only that there were wives who cheated their husband.
On the first day nothing happened, on the second day still nothing, a whole month went by and nothing happened. The councellors said to the Sultan that it wasn’t such a good idea. But the Sultan said that he had every confidence in his people. An he was right.
One night suddenly all the cheating wives were killed by their husbands, and strangely enough only the cheating wives.

At what night was this and how was this possible?

[Stewie]

are we allowed to discuss the answers here? and were wa this discussion in the first place?

EDIT: oh, I just figured out where it was discussed in the first place. Can we say what we think the answer is here?

[Norinel]

I don't believe there are any rules per se, just try not to spoil people's enjoyment too much without spoiler tags or whatever.

[Stewie]

spoiler marks... that reminds me, yesterday a guy in another forum worte something like "Why [mayor event here] in matrix revolutions?" in all caps as topic title. I just wanted to kill the bastard. Anyways, can it be for kerplunk's wife thing that the most obious answer is the correct one, and that the day in which all the wifes are killed is the one that each husband catches his wife doing it with the other guy? It's not likely, but worth a shot. Pm me if that was the answer, Kerplunk. And when I first read the topic title, I remembered another one, but now I forgot, so I'll try to remember.

[Cadmium]

If you're interested in these kind of things, you guys should just visit the Grey Labyrinth.

Watch out for chainsaws though .

[Wacky]

You can find the equivalent q and answer of the cheating wives problem by googling for "william wu". He runs some kind of puzzle site which I don't go to anymore (and deleted the bookmark)

And the truth/fibkin q and answer.

[mathcam]

To move this puzzle over...

Monty Hall is definitely another cool problem. Here's a simple also very cool related one.

A guy comes up to you with two envelopes with money, one has, say, X dollars, and the other has 2X dollars. He gives you one of the envelopes, you open it, count the money, and then he offers you a chance to switch envelopes if you want. Do you take it? (Say, for example, the envelope you opened had 50 bucks in it).

Well there are basically two possibilities. Either you lose $25 or gain $50(the other envelope is either going to have $25 or $100 in it). I suppose the best guess would be to switch, as you can't lose everything, but you stand to gain 100% if you're lucky.

Okay, good. Switching is the best answer...you're expected profit is .5*25+.5*100=$62.50, where as the expected profit of keeping the $50 is quite clearly $50.

So the first step is done. Now, consider the fact that you didn't need to know the value was $50. This would have worked for any postive integer (or real number, but let's keep this imaginable). But since it worked for any positive integer, you didn't even need to open the envelope in the first place, right? Your strategy should be to always switch.

The next thought coming through your head should be: WHAAAAA? He gives me one envelope at random, and my optimal strategy is to always switch? How can that possibly be right? Continuing this scenario, if he let you switch envelopes back, it would still be optimal for you to do so.

So your optimal strategy seems to be switching envelopes back and forth until the end of time. Your job is to figure out what's going on.

Cam

[mathcam]

p.s. I think you won't find this one on puzzle sites unless some like-minded mathematician has posted it there.

Cam

[Kerplunk]

*thinking about Norinel's problem and Cam's*

'Another' solution to the Monty Hall/quizmaster problem:

You have to switch when you are standing behind a 'false' door. The chance of standing behind a false door is 2/3. So, if you switch, the chance of coming from a false door and thus going to the right door is 2/3. Not switching is only the right thing to do, if standing behind the right door and that chance is 1/3.

[Quailman]

For the cheating wives:

Each man either knows about the total number (which does not include his wife), or one less than the total (because his wife is cheating). He also knows that each other man knows either the same number of cheaters that he does, or one more, or one less.

If one woman was cheating, then her husband would have been the only man not to know any cheating women, and would have killed her on the first night. If no woman was killed the first night, then the two men who only knew of one women would kill their wives, because they now know that everyone knew of at least one cheater. Since they themselves only know of one, their wives must be the second cheater that all but the two of them know. Or if no one died the second night, then the three men who only know of two women would kill their wives, and so on. So on the 40th night, the 40 men who know of 39 cheating women who did not die the night before will each kill their wives, because they now know that more than 39 women are cheating.

[Norinel]

Mathcam, I know I've read about it in some old Martin Gardner collection, but I can't recall the particular reasoning that counteracts the paradox. Thanks for putting one up I didn't already know the answer to (Though I did at some point).

[Strong Bad]

mathcam, the optimal strategy is clearly to keep switching envelopes until the other guy gets bored and leaves, then you get both, and earn between 1.5 times the ammount in envelope and 3 times the amount in the envelope.

[Antrax]

Re: mathcam,

I don't agree with the expectancy calculation here. Two envelopes, one with n and the other with 2n money. You're holding something that has 50% of being the n envelope, and 50% of being the 2n, together we have an expectancy of 1.5n, and it won't change if you switch.
Antrax

[Norinel]

I thought about that argument as well, but it seems like since n, from the perspective of the person who's opened one envelope, could be two different things, you can't treat it as a constant in that way.

[CaptainBlicero]

Now, consider the fact that you didn't need to know the value was $50. This would have worked for any postive integer (or real number, but let's keep this imaginable). But since it worked for any positive integer, you didn't even need to open the envelope in the first place, right? Your strategy should be to always switch.

Add the word "once" to the end of the last sentence. If you take the first envelope and open it, then you see that it contains X dollars. Keeping that envelope gives you an expected payoff of $X. Switching envelopes gives you an expected payoff of (.5*.5X) + (.5*2X) = $1.25X. Switching again obviously reduces your payoff back to $X. Therefore, it wouldn't be optimal to switch back.

If you never open the envelope, but to just pick one at random (or continually keep switching and just stop at a random point), your payoff is (.5*X) + (.25*.5X) + (.25*2X) = $1.125X, not $1.5X. Obviously, the best strategy is still to switch once, but it's better to pick an envelope at random than to simply keep the one you first open. Very interesting.

[mathcam]

Antrax: A little confusion here, which Norinel pretty much explained. Your "n" is the amount of money in the envelope you're currently holding. There is a 100 percent chance that the amount of money in your envelope is "n", so that is the expected value of not switching.

The expected value of

switching

is half of (n/2) plus half of (2n), i.e. 1.25n.

I think working out the case where you get the envelope with $50 in it should convince you.

CB: You're quite right that you're payoff goes back to X, but note that the same argument still applies. After you've switched, call the amount of money in your envelope Y. Then the other envelope either has Y/2 or 2Y again, giving us an expected value of 1.25Y to switch back, thus making it optimal. Weird, huh?

Obviously, the best strategy is still to switch once, but it's better to pick an envelope at random than to simply keep the one you first open. Very interesting.

But yeah, this is the more important question. It's not even just "the first one you open". It's the first one you're handed. Whichever one you're handed, the theory says you should take the other one, which is clearly nonsensical. There's something definitely fishy going on, but what?

Cam

[CurtainDog]

I think the problem is that n is unbounded, therefore your expected payoff before looking at either envelope is infinite.

As soon as you put a bound on the value of n you have to consider the possibility that the envelope you hold has the 'maximum amount'. Because swapping if you have the maximum will always lose you half of what you had this will reduce your expected gain from swapping envelopes to 0, i.e. there is no advantage to swapping.

The sum to infinity of 1/2^n is 2. So if you lost half the maximum (which is 1 in this equation) you'd lose a quarter of the potential value of all the envelopes. This takes care of the phantom .25 'advantage' you gain by swapping.

The net result is kind of like a monty hall situation with an infinite number of doors. There would be no point in swapping regardless of how many other doors have been opened.

[Dourgrim]

DISCLAIMER: I'm really bad at theoretical logic puzzles like these, so take my comment with a grain of salt.

So if, in the case of the envelopes, it is always advantageous to switch between the two envelopes (and an infinite number of times, at that), doesn't that also translate to it being advantageous to not bother switching at all? I mean, since the other envelope is statistically better, you're always going to go for it... but then, the second time around, you're statistically better off going back to the envelope you had the first time, et cetera. Why bother switching at all if you're going to cycle through the same two envelopes over and over?

[CaptainBlicero]

CB: You're quite right that you're payoff goes back to X, but note that the same argument still applies. After you've switched, call the amount of money in your envelope Y. Then the other envelope either has Y/2 or 2Y again, giving us an expected value of 1.25Y to switch back, thus making it optimal. Weird, huh?

Hm. It's been a few years since I took a probability course, but I'm pretty sure there's some special steps you have to take when looking at the expected value of an unknown quantity like Y. I can't point out precisely what's wrong though.

t's not even just "the first one you open". It's the first one you're handed. Whichever one you're handed, the theory says you should take the other one, which is clearly nonsensical.

No, that's not what I'm saying. I'm saying you should always take the envelope that has the unknown quantity.

Think about it this way: The man performs this test on you a sufficient amount of times for the probabilities to work out near-perfectly (for simplicity's sake, let's say 100 times is enough).
Each time, the envelope you first open has $50 in it. What is the optimal strategy?
E[always stay] = $50*100 = $5,000
E[always switch] = $100*50 + $25*50 = $6,250
E[switch half the time, stay half the time] = $50*50 + $100*25 + $25*25 = $5,625

This matches with the results I had earlier.

[mathcam]

So if, in the case of the envelopes, it is always advantageous to switch between the two envelopes (and an infinite number of times, at that), doesn't that also translate to it being advantageous to not bother switching at all?

This is essentially the paradox before us. Our expected value calculation shows that switching is always right, yet common sense dictates that this strategy is absurd.

No, that's not what I'm saying. I'm saying you should always take the envelope that has the unknown quantity.

Yes, and that is true for the case where you opened the envelope and found $50. But I'm saying the next interesting generalization is that the "always switch" result still holds if you didn't open the envelope at all. You're simply handed the envelope with some unknown amount of money in it, you're not allowed to open it, but you

are

allowed to switch envelopes if you want. Our calculation above shows that it's always right to switch, but after you've switched, the same argument holds again!

But yes, the proverbial nail has been hit on the head:

[quote="CurtainDog"I think the problem is that n is unbounded, therefore your expected payoff before looking at either envelope is infinite.[/quote]

We have that the expected value of staying is X, and the expected value of switching is 1.5X. This is only a contradiction of common sense if 1.5X>X. However, X is infinite. To convince yourself of this, if it weren't infinite, what would it be? A million dollars? There sure are a lot more numbers bigger than a million than smaller than million, so there's no way that could be right. Same argument for a billion, a trillion, etc.

So the expected value of staying or switching is infinite. CurtainDog is also right that as soon as we restrict the problem to a finite set of possible values the paradox disappears.

Hope that was enjoyable...I'll let you know if I find more.

Cam

[gslamm]

One hundred ants are placed on a stick one meter long. Each
ant begins to travel either to the left or to the right at a constant
speed of one meter per minute. When two ants meet, they bounce
off and reverse direction while maintaining their speed. When an
ant reaches either end of the stick it falls off.
What is the longest amount of time one must wait to be sure that
the stick is completely ant-free?

[mathcam]

Good ol' Macpow.

Cam

[gslamm]

macpow? MSRI !

[mathcam]

I think something like "Macallister Problem of the Week." I think that was last week's problem, or maybe the week before's.

Cam

[CurtainDog]

Hehe... bouncing ants. It'd be so much easier if they just walked around eachother