Life In 19x19

Magicwand wrote:

Redundant wrote:Magicwand

You can see that there is new information by looking at whether everyone knows the statement "If there were only one person with a red spot, would he know".

Without the visitor, they don't know this statement, but with the visitor's statement they do.

yes..only time the info is useful is when there is only 1 person.
but if more than 1 person then it is same info as tourist's info everyone are aware of the fact that there are at least one red spot.
if that is the case then there is only 1 possiblity for that island. there was only 1 red spot when tourist announce the info.

what am i missing?

Magicwand wrote:

Redundant wrote:Magicwand

You can see that there is new information by looking at whether everyone knows the statement "If there were only one person with a red spot, would he know".

Without the visitor, they don't know this statement, but with the visitor's statement they do.

yes..only time the info is useful is when there is only 1 person.
but if more than 1 person then it is same info as tourist's info everyone are aware of the fact that there are at least one red spot.
if that is the case then there is only 1 possiblity for that island. there was only 1 red spot when tourist announce the info.

what am i missing?

robinz wrote:Bandits and villagers:

It simply needs to be agreed that the first villager to be asked will say "red" if he sees, among the other 99, an odd number of red hats, and "black" if he seems an even number of red hats. (Or the other way round - the choice is arbitrary, although somewhat crucial for the unfortunate first villager!) Then this first villager has a simple 50-50 chance of giving he "correct" answer as regards his own hat colour, but the other 99 villagers can now each determine their own colour simply by counting those they can see (other than the first villager) and comparing it to the message given by the first one.

PS: isn't it nice of bad guys in these kind of puzzles to always actually pose a solveable puzzle, rather than just killing the lot of them

HermanHiddema wrote:A rather more cruel bandit, one who laughs at the idea of giving his prisoners a 99.5% chance of all being let go, decides to put his prisoners through a rather more cruel puzzle

He tells his 100 prisoners that tomorrow, he will allow them a chance to win their freedom. He has placed in a room 100 boxes, marked on the outside with the numbers 1 through 100. In each box, he has put a piece of paper with the name of a single prisoner on it. Tomorrow, each prisoner will be given the chance to inspect the contents of at most 50 boxes. If he finds the piece of paper with his name on it in one of those 50 boxes, he has succeeded. If he does not find his name, he has failed. If any prisoner fails, all of them will die. If they all succeed, they will be set free.

The prisoners are allowed to devise a strategy tonight, but tomorrow they will be unable to communicate during the procedure. Prisoners cannot leave messages in any way. They cannot mark boxes, or leave them open, move or remove papers, fold papers, etc, etc. Each prisoner will find the room, the boxes and their contents in exactly the same state.

If each prisoner opens 50 boxes at random, he will have 1/2 = 50% chance of finding his name. Altogether, randomly opening boxes gives the prisoners a 1 in 2^100 chance of surviving. About 0.000000000000000000000000000008%. Long odds.

So now, it is up to you: Devise a strategy that maximizes the prisoners' survival chances...

tj86430 wrote:Is the result of a single prisoner known to others immediately after (s)he has opened all his/her boxes? (i.e. if e.g. the first one fails, will the others immediately know that he has failed?)

flOvermind wrote:

tj86430 wrote:Is the result of a single prisoner known to others immediately after (s)he has opened all his/her boxes? (i.e. if e.g. the first one fails, will the others immediately know that he has failed?)

That doesn't really matter, they can just assume everyone before them has succeeded.

Assume the other prisoners don't know the result of the previous prisoners. They can still safely assume that all of them succeeded. Because if they are wrong, their future actions can't affect the outcome anyway, so it doesn't matter what they do.

tj86430 wrote:Ok, in that case my solution attempt:

The first 50 prisoners all open the same boxes (e.g. numbers 1-50, doesn't matter which as long as they are the same for all). If they all succeed, the rest will open the other 50 boxes

The probability of the random solution is 1/2^100 = 7.8886 * 10^-31.

In your solution, the probability of the first prisoner surviving is 50/100. The second prisoner has 49/99, the third one 48/98, and so on...
That is, the probability of the first 50 prisoners being right is 50! * 50! / 100! = 9.9 * 10^-30.
Then the other 50 prisoners are all correct.

That's only marginally better (about factor 12 ).

entropi wrote:prisoners

entropi wrote:prisonersThe only information transfer between the prisoners (during the procedure) is the fact that the previous ones could find their box, because otherwise they would be killed.

It has a binary search kind of feeling but I couldn't get anywhere with that.

Let's try another way:
If there were two prisoners and two boxes, it's easy.
If they pick up randomly the chance of survival is just 25%

But the simple strategy would be the first prisoner opens the first box and the second one opens the second box. Since after the first box they were not killed (50%) it is sure that the second prisoners name is in the second box. Thus the survival chance raises up to 50%.


The same principle should also apply if there are more boxes. Why? Why not?

So my proposal is: 1st prisoner opens boxes 1-50
2nd prisoner opens boxes 51-100 (the idea is since first prisoner survived, the chance that his name is in one of the 51-100 boxes is higher).

Now since both first and second have survived, the third prisoner has again no clue
Then he picks boxes 2-51

4th prisoner 49-99
5th prisoner 3-52
6th prisoner 48-98

etc.

Did you calculate the probability of success? I feel it is lower than in my solution, but I'm not sure

entropi wrote:They agree on something such that everyone survives with a probabilty of 99,5%. What is the idea?