Logical puzzles

[tj86430]

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?

I think someone already explained this, but let me try:

- If there is only one person with the red spot, (s)he will leave after the announcement, since (s)he realises (s)he has red spot
- If there are exactly two persons with the red spot, each will see one person with the red spot. If that person was the only person with the red spot (s)he would leave after the announcement (see above). Because the other one didn't leave when it was due, they will both know they have red spots and leave the day after
- If there are exactly three persons with the red spot, each will see two persons with the red spot. If those persons were the only persons with the red spot they would leave after the announcement + 1 day (see above). Because the other two didn't leave when it was due, they will all know they have red spots and leave the day after
- etc

e: slow

[entropi]

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, exactly that is the beauty of that puzzle.

If there are two red spots. Before the tourist says anything: Each one of them already knows that there is at least one red spot (all the non-red spots know that there are either two or three red spots, but that's not important).

But none of the red spots expect the other to leave, why? Let's call the red spots A and B.
A knows that B has a red spot.
But A also knows that B has no idea of his own spot. Therefore he does not expect B to leave next morning.

Once the visitor gives the information that there is at least one red spot, A learns the following:
If B is the only red spot, he will learn the color of his spot and leave the island next morning.

But the next morning B does not leave the island because he does not understand his color. This means that there must be at least one more red spot. Since A sees no red spot other than B, the only possibility is that A has a red spot himself.

So the information comes from the fact that A expects B to leave next morning but B does not leave.



Then imagine the case there is still one more red spot: A, B, C

A would think as follows:
I see only two red spots B and C. If I have a non-red spot, then B and C will leave in two days (for the reasons explained above).
But since B and C don't leave in two days, A understands that there must be at least one more red spot on the island, which cannot be anybody else than himself.
Thus, they all leave together after 3 days.
So goes on...

[Magicwand]

i think i understand..but it is profound!
much harder than go problem.

[entropi]

Another one:

Bandits fall upon a village with 100 inhabitants.

The bandit chief organizes a meeting with all of them and says:
"I have red and black hats. Tomorrow morning I will randomly put either a red or a black hat on each one of you. You won't be able to see your own hat but you will be able to see all the others.
Then I will ask each one of you one after the other the color of his head. Everybody will be able to hear his answer. He who knows his color will survive, otherwise he will be killed.

During the night, the logic master of the village comes up with an idea. They agree on something such that everyone survives with a probabilty of 99,5%. What is the idea?

[robinz]

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

[entropi]

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

correct

[HermanHiddema]

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]

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...

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]

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]

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.

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

[flOvermind]

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

That's similar to my attempt, but that's not really that much better than the pure random solution. I don't know the correct solution myself, either, but there must be something better than that

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 ).

[tj86430]

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 ).

That's what I calculated as well. Sadly, I couldn't come up with anything better.
One alternative was that the first prisoner checks boxes 1-50, the second one checks 51-100, third one checks again 1-50 etc. That is better than 1/2^100, but worse than my proposed solution.

[entropi]

prisoners

The 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.

[tj86430]

prisoners

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

[hyperpape]

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

Isn't it the case that the probability that they all survive is 50%? The last 99 are guaranteed to survive, the first has even odds. Perhaps you meant that the expected number of surviving villagers is 99.5? Or did I misread something?