What's your favorite lateral thinking puzzles?

The Game Room
41

I think a possible solution is also 5, 4, 3, 1. You assumed that everyone at the minimum. But they could also have eaten the maximum. True, Socrates saying “I don’t know” means that he ate more than one, but it also means he ate less than 5.

You see, Plato had to ask the question in the first place. He knows that there are at least 3 other cakes out there (one for everyone else). That leaves 10 left over. If he had eaten 6, then no one could possibly have eaten more than him. The most it could have been was 6, 4, 1, 1. So he wouldn’t “dream of asking a question to which he already knew the answer.” So you know that he had between 1 and 5.

Socrates similarly gets reasoned out. He must have had 2-4, otherwise he’d be able to say yes or no. Same goes for Dio, who must have had between (you guessed it) 3 and 3. So 3.

So there could be a max of 12 cakes out there or a minimum of 6. That Since Aristotle knew how many he had, it must have been the leftover 1 or 7.

So my solutions:
1, 2, 3, 7
5, 4, 3, 1

How do you determine it?

42

Exactly. The simple item I’m talking about will only help at the 14 coin level. After that, I think you’re always going to need more than 3 weighings.

43

Not quite. I’m saying that under these circumstances of complete ignorance, it is reasonable to take what is sometimes called the “robust optimization” approach to the problem. Because we don’t know anything about the way that Monty will behave when he is opening the door in the middle of our game, we want a strategy that will maximize the probability of winning the car in the worst case scenario. Put another way, we want to maximize our minimum probability of winning.

Perhaps I can illustrate the “minimum probability of winning” by way of an example. Suppose this time, Monty Hall has some psychic powers–he can read the mind of anyone who is sufficiently close. After the car and two goats have been placed behind the doors, you walk on stage and Monty reads your mind. Monty then adjusts his own behavior so that he minimizes your chances of winning the car (this is the “minimum probability of winning”). An example is in the Spoiler box below, but it might give a big hint for the original problem for anyone who hasn’t solved it yet:

Suppose you choose door 1, and decide that you will switch if he opens door 2, but stay if he opens door 3. Then Monty’s strategy is to open door 2 if it is availabe, and open door 3 otherwise. In this case, you will win with probability 1/3 (if the car is behind door 1, Monty opens door 2 and you switch to a losing door; if it is behind door 2, Monty opens 3 and you stay at a losing door; if the car is behind door 3, Monty opens door 2 and you switch to the winning door).

Now that we’ve defined our minimum probability of winning, the robust optimization problems asks us to find a strategy which maximizes this “minimum probability of winning.” In fact, the canonical strategy is the solution to the robust problem.

If I did my calculations correctly, the canonical solution of “always switch” wins with probability 2/3 no matter how Monty decides to open a door. Furthermore, even if you know the distributions that Monty uses to make his decision, no strategy with beat the “always switch” strategy. However, if Monty uses a strategy like “always open the left-most available door”, other strategies will tie the “always switch” strategy.

I should note that, the solution to the robust optimization problem and the problem described by “If you don’t know anything else, you should assume the problem intends the ‘uniform’ marginal as your distribution” aren’t always the same. They just happen to be the same in this case.

Upon re-reading, I should also note that all my analysis was done assuming that the car was equally likely to be behind any of the door. I believe that this assumption is fairly general, see below.

Sure, independence is still an assumption, but it’s an assumption that can be made in virtually any realistic situation (you could, after all, roll a die to make your decision before you leave home to go on the game show). In realistic scenarios, the assumption that the location of the car is uniformly distributed is fairly likely to be false (unless they use a computer or roll a die to decide where to put the car).

44

Fair enough; if your goal is to pick a strategy which, with access to a source of randomness independent from anything Monty has access to, maximizes your minimum probability of winning across all distributions for Monty’s behavior (where the only freedom Monty has in his behavior is to pick which of the two doors you didn’t pick to open in case they both contain goats), then you should initially pick a door at uniform random and then switch, ensuring you will win just in case your initial door did not contain the car, which happens with probability 2/3 since you pick it at independent uniform random. It will not be possible to do better than this because Monty could always choose, with access to a source of randomness independent from anything you have access to, to place the car at uniform random behind a door, and to open a door at uniform random from those he is allowed to, in which case your first choice of door has 1/3 probability of being correct, independently of which door he opens, so you will have a 2/3 winning chance if you switch and 1/3 if you stay. I agree with all that.

That having been said, one could hardly be blamed for interpreting “What should you do?” to potentially mean something other than “What should you do to maximize your minimum probability of winning across all distributions for Monty’s behavior?”. I would prefer that whatever the meaning intended for “What should you do?” be made explicit. (There is something canonical to the canonical solution, of course; I have no opposition to framing the problem in such a way as to naturally force this. For example, suppose you aren’t told which door Monty opens, only that he opened one of them and it contained a goat and you have the opportunity to switch to another. Then you can’t possibly gain any information from learning which particular door Monty opens, so the canonical solution enters in full effect (given the below))

I agree; I was being very pedantic in pointing it out as an assumption, but was doing so simply to stress the point that there are hidden assumptions in every probability puzzle, which must be teased out before one can attempt to answer them.

45

Socrates could have had 2 to 5 cakes, not 2 to 4. If he had 5, Plato could also have had 5, so he wouldn’t know whether he had more than Plato. Likewise, Diogenes could have had 3 to 5 cakes.

If you then assume that Aristotle had 1 cake (or any number less than 7), there are multiple possibilities for the distribution of the other cakes. But if he had 7 cakes, there is only one possible distribution.

46

Dr. Love, you’re still making unjustified assumptions about Monty’s behavior. It’s also possible that Monty follows this script:

1: If you picked the correct door, Monty offers you the opportunity to switch to one of the other two, selected randomly.
2: If you picked the wrong door, Monty immediately opens it and says “Congratulations! You’ve won a dirty sock!”.

If Monty is using this strategy, then your strategy of “always switch” is guaranteed to always give you the worst possible outcome, and a strategy of “never switch” is guaranteed to always give you the best possible outcome.

Now, in actual fact, Monty behaved somewhere in between this and the “conventional model” of always opening a door. He would either open another door or nor, and either offer a switch or not, based on which behavior he personally thought was most likely to result in the contestant losing. And he was pretty good at it, too.

47

Two old favorites suitable for students:

There are two jugs, one of which holds 3 exactly gallons of water and the other holds exactly 5 gallons. Using only these two jugs and an unlimited supply of water, put exactly 4 gallons of water into the 5-gallon jug (or a bomb in a children’s park will explode!)

One of several solutions:

Fill the 5-gallon jug. Use it to fill the 3-gallon jug. Empty the 3-gallon jug. Pour the 2 gallons from the 5-gallon jug into the 3-gallon jug. Fill the 5-gallon jug. Use it to fill the 3-gallon jug, leaving 4 gallons in the 5-gallon jug.

Four men are arrested for a crime, but the jail is full. The warden decides to give them a game–if they succeed they can go free but if they fail they are executed.

The warden explains the game:
He will put three of the men sitting in a line, facing in the same direction (let’s call them “A”, “B”, and “C”; “A” is at the back of the line.). The fourth man (“D”) will be put in a separate room, where he can’t see or be seen by any other prisoner. Each man will have a hat put on his head; two of these hats are white and two are black. The prisoners can see the hats in front of them but not on themselves or behind. If any prisoner can say out loud what color hat he has on his head, all four prisoners go free. No communication other than saying “white” or “black” is allowed during the game itself.

The prisoners are then allowed to formulate a strategy to guarantee their survival. What strategy should the prisoners use?

“A” says either “black” or “white” if he observes that “B” and “C” both have white or both have black hats, respectively. If the two men in front of him have different color hats, he says nothing. After an appropriately long wait, “B” can conclude that he is wearing a different color hat from “C”, and says either “black” or “white” if he observes that “C” is wearing a white or a black hat, respectively. “C” and “D” say nothing.

48

What’s the point of prisoner D in your setup?

Anyway, there’s an easier solution: B announces the color of C’s hat, then C repeats it.

ETA: Ah, nevermind, I get it now. There was that business about two blacks and two whites, and implicitly, no prisoner is allowed to make a wrong announcement, even if another makes a correct announcement. Makes sense.

49

There’s a whole series of these prisoner problems. My favorite, though it’s pretty intense, is that there are infinitely many prisoners in a line, Prisoner #1 at the front, Prisoner #2 behind Prisoner #1, Prisoner #3 behind prisoner #2, and so on, one for each positive integer. Each has a word written on their hat; “dog”, “green”, “Brobdingnagian”, or so on. Each can only see the hats in front of them. The warden will ask each prisoner to guess the word on their own hat; the prisoners will not be able to hear other prisoners’ guesses or communicate in any way once the game starts. If infinitely many prisoners get it wrong, then the whole gang is killed; however, if all but finitely many prisoners get it right, the gang is free to go. Before the whole thing goes down, the prisoners meet to devise a strategy. How can they guarantee they’ll be set free?

50

Ack, I meant to say: Prisoner #1 is at the back of the line, Prisoner #2 is in front of Prisoner #1, Prisoner #3 is in front of Prisoner #2, and so on.

There are no other mistakes in the setup, though you won’t believe me.

51

As for the solution, I explained it in detail in this thread, starting with post #69. However, I’ll re-explain it:

For any particular sequence of head-labels, there are various sequences of guesses which would constitute a win (specifically, any sequence of guesses which matches the sequence of head-labels at all but finitely many spots). Let’s say these guess-sequences comprise the “winning set” associated with that sequence of head-labels. The key is that, although each prisoner only has partial information about the actual sequence of head-labels, they still have enough information to determine what the winning set associated with the actual sequence of head-labels is, since there are only finitely many heads whose labels they don’t know, and a sequence of guesses is allowed arbitrary finite leeway in winning (that is, a sequence of guesses will match the full sequence of head-labels in all but finitely many spots just so long as it matches the sequence of visible head-labels in all but finitely many spots, from any prisoners’ point of view). Accordingly, what the prisoners do ahead of time is pick, for each possible winning set, a designated guess-sequence from that set; when the game is actually played, each prisoner figures out what the actual relevant winning set is, and guesses according as to the corresponding designated guess-sequence, guaranteeing that the full guess-sequence played is actually one which will win.

That’s a bit of a rushed explanation, but it hopefully gets the basic idea across.

52

Ack, let’s leave the Monty Hall problem out of the thread…everybody knows the answer is wrong anyway. :smiley:

53

I disagree. No matter what Monty’s typical behavior, I had a 1/3 chance of my first guess being correct. If a goat is then revealed and I’m asked to switch, switching gives me a 2/3 chance to win. Not 100%, mind you, but twice what I had. IMO the problem as posted (copied directly from wiki) is sufficient.

54

This is the very nature of probability problems. When you’re trying to reach a goal, you often have to define exactly what you mean by reaching it probabilistically. There is almost always more than one way to view your goal, and these views usually lead to conflicting solutions.

Yes, this is usually true. However, for this problem, I’m fairly convinced that there is only one best strategy that works regardless of what the initial distribution of the prize is, and regardless of what door Monty chooses to open.

Really? The SDMB isn’t a journal of mathematics, and I don’t expect the problem statements to be as rigorous as they would be for a journal. If it were possible that Monty followed that script, then Ellis Dee’s problem statement would have said so. Otherwise, I doubt that a single problem has been posted so far that couldn’t be creatively interpreted so that the so-called “solution” is actually not a solution.

55

I’ll add another fun riddle to this, which I’ve heard before:

100 days later, all 100 blue-eyed islanders kill themselves.

56

Ok, I’ll explain the answer once and then let’s stop bothering with the Monty Hall problem, please? :smiley:

There are 3 places where the car can be:
Car in A
Car in B
Car in C

So, there are 9 possible combinations of player choice + car location:
Car in A, Pick A
Car in A, Pick B
Car in A, Pick C
Car in B, Pick A
Car in B, Pick B
Car in B, Pick C
Car in C, Pick A
Car in C, Pick B
Car in C, Pick C

In 3 of the 9 choices (33%,) staying with the same door wins() the car:
Car in A, Pick A
Car in A, Pick B
Car in A, Pick C
Car in B, Pick A
Car in B, Pick B*
Car in B, Pick C
Car in C, Pick A
Car in C, Pick B
Car in C, Pick C*

However, if the other wrong door is removed, switching will win() the car 6 out of 9 times:
Car in A, Pick A, B or C removed, switch to B or C.
Car in A, Pick B, C removed, switch to A.
Car in A, Pick C*, B removed, switch to A.
Car in B, Pick A*, C removed, switch to B.
Car in B, Pick B, A or C removed, switch to A or C.
Car in B, Pick C*, A removed, switch to B.
Car in C, Pick A*, B removed, switch to C.
Car in C, Pick B*, A removed, switch to C.
Car in C, Pick C, A or B removed, switch to C.

Therefore, if you always switch, you double your chances of winning a car from 1/3 to 2/3.

This is considered the canonical answer.

However, IMHO, this is the wrong answer because everybody knows it’s no longer out of 9 when you remove one door.

Without going through all the examples, you now have 6 possible combinations. Staying with the same door wins 3 out of 6, switching wins 3 out of 6.

57

Oh, shit, what have I unleashed?

Superhal, in the canonical presentation of the problem, you will win upon staying just in case you originally picked the right door, and you will win upon switching just in case you originally picked a wrong door. Accordingly, the probability of winning when you stay is the same as the probability that you originally picked the right door; the probability of winning when you switch is the same as the probability that you originally picked a wrong door. Do you really feel that the probability that you originally picked the right door and the probability that you originally picked a wrong door are both 3/6?

Certainly, we can rig a probability distribution to give that result under suitably lax restrictions; that is part of what I was emphasizing about the need to make the intended probability distribution explicit. But I doubt you would find that rigged probability distribution to be the appropriate one to use on most criteria.

58

I thought you were kidding. You really think it’s 50/50 after a wrong door is revealed?

How about using a deck of cards instead. Pick a random card, looking for the ace of spades. I’ll go through the deck and show you 50 losing cards. Now, do you stay with your original choice, or switch to the only other card left?

Do you think this scenario is 50/50 as well? Why or why not?

59

To Superhal: It’s worth noting: just because an event has n different ways of happening, doesn’t mean each of the n ways has equal probability of happening. This is the flaw in your reasoning. (You also may be using an analysis on which your problem is forgetting to account for the extra information you gain when Monty opens a door; the fact that he chose this door, as opposed to that door, is potentially relevant extra information about the situation at hand, and extra information is the drive behind shifting of conditional probabilities)

60

It could be 5 million cards, the final choice will still be 50/50, as long as the correct choice is included in one of the two final cards.

The problem with this and the original puzzle, is the definition of “probability.” The number of wrong doors artificially increases the probability away from the final choice. By removing one of the wrong doors after the player chooses forces the equation to include the 3rd door.

In the case of 5 million cards, my chances of winning (by the original definition of probability) is 1 out of 5 mil for not switching and 4,999,999 out of 5 million for switching, which is also nonsensical.