Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Galzria]

What if they agree to all yell "Black" if anywhere in front of them they see even a single black hat, otherwise they yell "White"?

This would mean that any person wearing a Black Hat will guess Black if any person in front of him has a Black hat on. And if nobody does, then every person in front of him will guess correctly (even though he is wrong). This guarantees some number X of infinity will be correct.

The difficulty isn't getting an infinite number of correct solutions. It's getting a finite number of incorrect solutions.

But this gives you a guarantee of 1. Always. Every other guess may be wrong but you WILL have 1 correct. What's more, it's IMPOSSIBLE to have all guess correctly here. So your range is {1, (Infinity -1)}

[liopoil]

infinity minus one is infinity. You need a guaranteed finite number of incorrect answers.

[Ozle]

Separate them into infinite groups, then it becomes like every other hat problem?

[eHalcyon]

Separate them into infinite groups, then it becomes like every other hat problem?

But those hat problems don't have them speak simultaneously.

Also, I don't think there was a solution to a hat problem with 100% success for every participant.  So even if you separate them into infinite groups of finite people, each of those groups may have one incorrect, one incorrect in each of infinite groups is an infinite number of incorrect people.

[fractic]

Hi, long time lurker here. But since I'm doing a PhD in mathematics, I can't resist chipping in here. So here are two of my favorite logic/probablity puzzles.

First, we once again have a prison with 100 prisoners, who get one chance at freedom. In the courtyard 100 boxes are placed, each labeled with a name of one of the prisoners (all 100 are different). In every box there is a piece of paper. These pieces are also each marked with one of the prisoner's names (again all names are present). These papers have been distributed amongst the boxes completely randomly.

In an hour all prisoners will be called to the yard one at a time. They are allowed to open 50 of the boxes. If one of the boxes opened contains the paper with his name on it , the prisoner passes the test. If all 100 prisoners pass they are all allowed to go free, but if a single one fails they are all stuck inside. The prisoners have an hour to discuss their strategy. What is their best chance of getting out of jail?

To clarify, the prisoners are not allowed to move or otherwise manipulate the boxes and papers besides open 50 of them and see if they found their own name.


The second problem has a more cheerful setting. A princess has reached a marriageable age and no less then 100 suitors have shown up to the kingdom. The princess is now faced with the task of finding the best candidate for marriage. One by one the 100 suitors will present themselves to the princess and ask for her hand. The princess will have to give her answer right away.  If the princess rejects a suitor, he will be heart broken and will leave the kingdom immediately.

Fortunately our princess is gifted with a magical ability to judge the suitability of a suitor the second she lays eyes on him. We will assume that the suitability of a suitor can be judged on a linear scale. What strategy should the princess follow to maximize the chance of marrying the best suitor?

[Tables]

For the second problem, can we assume every suitor's suitability is independent of one another and uniformly distributed?

[fractic]

You can assume that no two suitors are equally suitable, and that they appear in a completely random order.

[Tables]

Ah, okay, but you cannot know where a suitor is in terms of rank? Just how suitable they are linearly?

In that case I think I've read the solution before in a book by Ian Stewart. It's pretty neat, and nice and mathematical IIRC.

[fractic]

Yes basically that. So if the princess sees the 10th suitor she immediately knows (for example) that he's better than 6 of the ones she saw before but worse than the other 3. But she has no idea how close this this 10th suitor is to the best one.

[Grujah]

And my second favourite:

10 people are captured by some psychopath, who offers them a chance of survival based the color of their hat, as is usual with psychopaths. All 10 of them get to confer, with the bad guy listening. After they're done talking or five minutes elapse (this psychopath is not big on loopholes) he magically makes either a white hat or a black hat appear on the head of each of them, with all hats appearing at the same time. Then they each write "black" or "white" on a piece of paper, give him the pieces of paper (all this without them talking to each other or seeing what other people wrote), he kills all those whose hat color doesn't match their and lets the rest go.

Your job is to find the strategy that ensures the most people survive in the worst case, and prove that this strategy is indeed the best (for the worst case).

I can get 50% in worst case. Here's how:

Beforehand, form 5 pairs of two persons in each pair, which each pair having a person labeled "X" and "Y". X guess the same color as Y's hat. Y guesses the different color that X's hat. So, in any case (BB, WW, WB, BW), exactly one of them will get the right answer (in each pair). So, definitely 5 right guesses.

No idea how to prove that there is no better strategy.

[Grujah]

Hi, long time lurker here. But since I'm doing a PhD in mathematics, I can't resist chipping in here. So here are two of my favorite logic/probablity puzzles.

First, we once again have a prison with 100 prisoners, who get one chance at freedom. In the courtyard 100 boxes are placed, each labeled with a name of one of the prisoners (all 100 are different). In every box there is a piece of paper. These pieces are also each marked with one of the prisoner's names (again all names are present). These papers have been distributed amongst the boxes completely randomly.

In an hour all prisoners will be called to the yard one at a time. They are allowed to open 50 of the boxes. If one of the boxes opened contains the paper with his name on it , the prisoner passes the test. If all 100 prisoners pass they are all allowed to go free, but if a single one fails they are all stuck inside. The prisoners have an hour to discuss their strategy. What is their best chance of getting out of jail?

To clarify, the prisoners are not allowed to move or otherwise manipulate the boxes and papers besides open 50 of them and see if they found their own name.

This was posted (but with dominion cards) somewhere already.

IIRC, idea is, that each prisoners needs to assume that guy that went in before him found what he needed, and work from that. But I'm lazy now.

[Grujah]

The second problem has a more cheerful setting. A princess has reached a marriageable age and no less then 100 suitors have shown up to the kingdom. The princess is now faced with the task of finding the best candidate for marriage. One by one the 100 suitors will present themselves to the princess and ask for her hand. The princess will have to give her answer right away.  If the princess rejects a suitor, he will be heart broken and will leave the kingdom immediately.

Fortunately our princess is gifted with a magical ability to judge the suitability of a suitor the second she lays eyes on him. We will assume that the suitability of a suitor can be judged on a linear scale. What strategy should the princess follow to maximize the chance of marrying the best suitor?

If it is better than at least X of them, where X is the number of remaining suitors, go for him?

[mith]

And my second favourite:

10 people are captured by some psychopath, who offers them a chance of survival based the color of their hat, as is usual with psychopaths. All 10 of them get to confer, with the bad guy listening. After they're done talking or five minutes elapse (this psychopath is not big on loopholes) he magically makes either a white hat or a black hat appear on the head of each of them, with all hats appearing at the same time. Then they each write "black" or "white" on a piece of paper, give him the pieces of paper (all this without them talking to each other or seeing what other people wrote), he kills all those whose hat color doesn't match their and lets the rest go.

Your job is to find the strategy that ensures the most people survive in the worst case, and prove that this strategy is indeed the best (for the worst case).

I can get 50% in worst case. Here's how:

Beforehand, form 5 pairs of two persons in each pair, which each pair having a person labeled "X" and "Y". X guess the same color as Y's hat. Y guesses the different color that X's hat. So, in any case (BB, WW, WB, BW), exactly one of them will get the right answer (in each pair). So, definitely 5 right guesses.

No idea how to prove that there is no better strategy.

Yep, that's it. As for proving it's optimal, the worst case can't be better than the average case.

[Grujah]

And my second favourite:

10 people are captured by some psychopath, who offers them a chance of survival based the color of their hat, as is usual with psychopaths. All 10 of them get to confer, with the bad guy listening. After they're done talking or five minutes elapse (this psychopath is not big on loopholes) he magically makes either a white hat or a black hat appear on the head of each of them, with all hats appearing at the same time. Then they each write "black" or "white" on a piece of paper, give him the pieces of paper (all this without them talking to each other or seeing what other people wrote), he kills all those whose hat color doesn't match their and lets the rest go.

Your job is to find the strategy that ensures the most people survive in the worst case, and prove that this strategy is indeed the best (for the worst case).

I can get 50% in worst case. Here's how:

Beforehand, form 5 pairs of two persons in each pair, which each pair having a person labeled "X" and "Y". X guess the same color as Y's hat. Y guesses the different color that X's hat. So, in any case (BB, WW, WB, BW), exactly one of them will get the right answer (in each pair). So, definitely 5 right guesses.

No idea how to prove that there is no better strategy.

Yep, that's it. As for proving it's optimal, the worst case can't be better than the average case.

well, Duh. 

[fractic]

This was posted (but with dominion cards) somewhere already.

IIRC, idea is, that each prisoners needs to assume that guy that went in before him found what he needed, and work from that. But I'm lazy now.

I checked this topic and the probability paradoxes one but didn't see it.

As for as the answer goes: Not really I think. Of course the prisoners can assume that the previous one succeed since they already lost otherwise. But there is no real point in doing this. In fact the optimal solution has every prisoner follow the same strategy not caring about what the previous guys did. They are trying to exploit a certain property that the distribution of the papers might have.

If it is better than at least X of them, where X is the number of remaining suitors, go for him?

Sorry but, This strategy will obviously frequently select a suitor that isn't even better than all the previous ones. All though if the princess is OK with an average candidate rather than the perfect one this strategy might be better.

[mith]

Hi, long time lurker here. But since I'm doing a PhD in mathematics, I can't resist chipping in here. So here are two of my favorite logic/probablity puzzles.

First, we once again have a prison with 100 prisoners, who get one chance at freedom. In the courtyard 100 boxes are placed, each labeled with a name of one of the prisoners (all 100 are different). In every box there is a piece of paper. These pieces are also each marked with one of the prisoner's names (again all names are present). These papers have been distributed amongst the boxes completely randomly.

In an hour all prisoners will be called to the yard one at a time. They are allowed to open 50 of the boxes. If one of the boxes opened contains the paper with his name on it , the prisoner passes the test. If all 100 prisoners pass they are all allowed to go free, but if a single one fails they are all stuck inside. The prisoners have an hour to discuss their strategy. What is their best chance of getting out of jail?

To clarify, the prisoners are not allowed to move or otherwise manipulate the boxes and papers besides open 50 of them and see if they found their own name.

Well, as a starting point: Each prisoner starts with their named box, then opens the box corresponding to the piece of paper, and so on until they either find their name or run out of tries. If the largest cycle contains 50 or fewer boxes, they will all succeed; otherwise, they will all fail. I am far too lazy to figure out what the probability of success is...

[jonts26]

The second problem has a more cheerful setting. A princess has reached a marriageable age and no less then 100 suitors have shown up to the kingdom. The princess is now faced with the task of finding the best candidate for marriage. One by one the 100 suitors will present themselves to the princess and ask for her hand. The princess will have to give her answer right away.  If the princess rejects a suitor, he will be heart broken and will leave the kingdom immediately.

Fortunately our princess is gifted with a magical ability to judge the suitability of a suitor the second she lays eyes on him. We will assume that the suitability of a suitor can be judged on a linear scale. What strategy should the princess follow to maximize the chance of marrying the best suitor?

Just to be clear, are we trying to maximize the chances that the princess picks the one very best suitor, or are we trying to maximize the expected suitableness of the suitor she does pick, or is the distinction not relevant?

[fractic]

Just to be clear, are we trying to maximize the chances that the princess picks the one very best suitor, or are we trying to maximize the expected suitableness of the suitor she does pick, or is the distinction not relevant?

We want to maximize the chances of the princess picking the best suitor. Maximizing for the best expected suitability probably involves a different strategy.

[Grujah]

This was posted (but with dominion cards) somewhere already.

IIRC, idea is, that each prisoners needs to assume that guy that went in before him found what he needed, and work from that. But I'm lazy now.

I checked this topic and the probability paradoxes one but didn't see it.

As for as the answer goes: Not really I think. Of course the prisoners can assume that the previous one succeed since they already lost otherwise. But there is no real point in doing this. In fact the optimal solution has every prisoner follow the same strategy not caring about what the previous guys did. They are trying to exploit a certain property that the distribution of the papers might have.

Here it is:
http://forum.dominionstrategy.com/index.php?topic=4644.0

(Spoilers obviously, ehunt posted (on page 2) what seems to be definite solution?)

I was wrong on strategy, completely

[mith]

Simpler calculation than I had feared. I should be less lazy.

[fractic]

Well, as a starting point: Each prisoner starts with their named box, then opens the box corresponding to the piece of paper, and so on until they either find their name or run out of tries. If the largest cycle contains 50 or fewer boxes, they will all succeed; otherwise, they will all fail. I am far too lazy to figure out what the probability of success is...

This is basically correct. I'll explain in the spoiler how it works.

Since the answer doesn't really depend on the number of prisoners, let's assume there are 2n of them and that they open n boxes each.
Each prisoner will first open the box with their name on it and then every time the box with the name that is on the paper in the previous box. If he could open as many boxes as he
wants this will eventually lead back to the box with his name on it, and therefore the previous box contained his own name. If you have trouble seeing this, consider
that there are only a finite number of boxes and that every box shares a name with only a single piece of paper.

The prisoners now escape if every one of them finds their own name within n boxes. So if there is a single cycle of n+1 or longer they will fail. It's easier to compute the probability of failure, so we'll do that. Now there can only be 1 cycle of n+1 or longer since there are only 2n boxes. Let k>n the chance that there is a k-cycle is

(number of ways to choose k names to go in the cycle)x(number of way to order them in the cycle)x(number of ways to permute the other 2n-k names)=(k!/((2n)!x(2n-k)!)x(k-1)!x(2n-k)!=k/(2n!)

So the total number permutations with a n+1 cycle or longer is (n+1)/2n!+(n+2)/2n!+...+n/(2n!). Since the total number of permutations is 2n! this means that the chance of failure is
exactly 1/(n+1)+1/(n+2)+...+1/2n.

Using the approximation for the harmonic series that says 1/1+1/2+...+1/n ~=~ log(n) we see that the chance of failure is approximately log(2n)-log(n)=log(2) ~=~0.69.

So our inmates have just over 30% chance of freedom.

Here it is.

I just typed up the solution myself too but thanks for the link.

[DStu]

I desperately want to give a hint on that one in light of one of DStu's posts...

In the meantime, here's my favourite hat puzzle:

There are four people. In five minutes, each will be given a hat which is black or white, each with probability 1/2, with each chance independent. Each may submit a guess if he chooses. If at least one person guesses correctly, and nobody guesses incorrectly, they will be released. Otherwise, all will be killed.

Can they actually do better than 15/16 ?

I get to 11/16

[Titandrake]

I desperately want to give a hint on that one in light of one of DStu's posts...

In the meantime, here's my favourite hat puzzle:

There are four people. In five minutes, each will be given a hat which is black or white, each with probability 1/2, with each chance independent. Each may submit a guess if he chooses. If at least one person guesses correctly, and nobody guesses incorrectly, they will be released. Otherwise, all will be killed.

Can they actually do better than 15/16 ?

I get to 11/16

The wording "may submit a guess" suggests that using/not using a guess can convey information. Designate two people as #1 and #2.

If #2's hat is black, #1 submits a guess, otherwise #1 does not try to guess. #2 can then guess hat color with 100% certainty. Fails if the guesses are simultaneous though.

I have seen this problem before, but didn't solve it at the time. It was for a team competition at a summer program I went to. It was a more general version though: In a team of 7 people, each member is given a number from 1 to 6. We just brute-forced it by all guessing 4.

[jonts26]

I desperately want to give a hint on that one in light of one of DStu's posts...

In the meantime, here's my favourite hat puzzle:

There are four people. In five minutes, each will be given a hat which is black or white, each with probability 1/2, with each chance independent. Each may submit a guess if he chooses. If at least one person guesses correctly, and nobody guesses incorrectly, they will be released. Otherwise, all will be killed.

Can they actually do better than 15/16 ?

I get to 11/16

You can beat that by guessing randomly.


The wording "may submit a guess" suggests that using/not using a guess can convey information. Designate two people as #1 and #2.

If #2's hat is black, #1 submits a guess, otherwise #1 does not try to guess. #2 can then guess hat color with 100% certainty. Fails if the guesses are simultaneous though.

No one knows if another person submitted a guess. See each others hats and then go to seclusion.

[Titandrake]

I desperately want to give a hint on that one in light of one of DStu's posts...

In the meantime, here's my favourite hat puzzle:

There are four people. In five minutes, each will be given a hat which is black or white, each with probability 1/2, with each chance independent. Each may submit a guess if he chooses. If at least one person guesses correctly, and nobody guesses incorrectly, they will be released. Otherwise, all will be killed.

Can they actually do better than 15/16 ?

I get to 11/16

You can beat that by guessing randomly.


The wording "may submit a guess" suggests that using/not using a guess can convey information. Designate two people as #1 and #2.

If #2's hat is black, #1 submits a guess, otherwise #1 does not try to guess. #2 can then guess hat color with 100% certainty. Fails if the guesses are simultaneous though.

No one knows if another person submitted a guess. See each others hats and then go to seclusion.

That's not stated in the problem, but if you assume that then I don't know.

I also missed the "nobody guesses incorrectly" line, which makes guessing randomly a pretty bad idea. Also have to modify the strategy to #1 or #2 not guessing tells #3 something.