Logical puzzles

[cyclops]

Three gods A, B, and C are called, in some order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, B, and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language, in which the words for yes and no are 'da' and 'ja', in some order. You do not know which word means which.

Ask A whether B wouldth confirm that C wouldth confirm that he is God.
If you get an answer then A is Random.
If he's not Random ask the similar question to B.
Now we know Random. The Others we call P and Q for God's sake.
Ask P if He confirms that da is Goddish for true. If He answers da he is True.

[hyperpape]

@cyclops

Ask A whether B wouldth confirm that C wouldth confirm that he is God.
If you get an answer then A is Random.
If he's not Random ask the similar question to B.
Now we know Random. The Others we call P and Q for God's sake.
Ask P if He confirms that da is Goddish for true. If He answers da he is True.

I believe your first question doesn't quite work, but it's on a useful track.

If A is false, B is true and C is random, A will say 'yes'. B will remain silent, because he cannot say whether C will answer, so A will be speaking falsely.

P.S. Adding to the confusingness of the puzzle, if he uses weak negation, True can say

Not(random would confirm that he is a God)

I think we're better off assuming that the Gods just fall silent when they can't answer.

[SpongeBob]

... Next problem.

on a strange island there lives a strange tribe of 300 perfectly logical and perfectly intelligent persons. And they know it of each other. Each member has a spot, red or black, on the back of the head. Nobody knows the color of his own spot but they do know the color of everybody else's. If a tribesman ever realizes the color of his own spot it is strict custom that he publicly announces this fact the next morning and leaves the island forever. So they never mention spot colors and have no mirrors. But one day a tourist, American OC, visits the island and announces to the entire tribe: "I can see at least one of you has a red spot!". The tourist leaves to return a year later.
He is surprised. Why?

What a wonderful puzzle I am still trying to understand the solution, though ...

The thing that bugs me: Let's say there are 100 islanders with a red spot and 200 islanders with a black spot. Now this guys comes and states that 'At least one of you has a red spot.' Well, so what? Everybody knew that already, right? So maybe he just started the process, because there has to be a starting point in time for the induction to take place. But then, if it was just the starting point, then he could as well have said 'At least one of you has a black spot' and thus the color does not seem to have any relevance - it is not clear why islanders with red spots are leaving the island and not islanders with black spots.

When I find time, I will read the article given above.

[Dusk Eagle]

If the islanders know that either their spot is black or their spot is white, I believe all the black-spotted people will leave the day after all the red-spotted people have left. However, if they do not know for certain that their spot is either red or black, then all the black-spotted people will be stuck on the island forever, not knowing if they personally have a spot that is a different color than everyone else's.

[cyclops]

@cyclops

Ask A whether B wouldth confirm that C wouldth confirm that he is God.
If you get an answer then A is Random.
If he's not Random ask the similar question to B.
Now we know Random. The Others we call P and Q for God's sake.
Ask P if He confirms that da is Goddish for true. If He answers da he is True.

I believe your first question doesn't quite work, but it's on a useful track.

If A is false, B is true and C is random, A will say 'yes'. B will remain silent, because he cannot say whether C will answer, so A will be speaking falsely.

P.S. Adding to the confusingness of the puzzle, if he uses weak negation, True can say

Not(random would confirm that he is a God)

I think we're better off assuming that the Gods just fall silent when they can't answer.

Ok, I'll hide as you prefer.
Alternative first question(s): Ask A whether Random would give the same answer as A would give if asked whether he is God. If A answers he is Random himself. The last question as before.

[SpongeBob]

... Next problem.

on a strange island there lives a strange tribe of 300 ...

What a wonderful puzzle I am still trying to understand the solution, though ...

The thing that bugs me: Let's say there are 100 islanders with a red spot and 200 islanders with a black spot. Now this guys comes and states that 'At least one of you has a red spot.' Well, so what? Everybody knew that already, right? So maybe he just started the process, because there has to be a starting point in time for the induction to take place. But then, if it was just the starting point, then he could as well have said 'At least one of you has a black spot' and thus the color does not seem to have any relevance - it is not clear why islanders with red spots are leaving the island and not islanders with black spots.

When I find time, I will read the article given above.

Slowly getting there:

At first it seems that if there are two or more islanders with a red spot, the announcement of the tourist does not change anything. But in fact, some information is added:
Before the announcement, everyone knew that there is at least one with a red spot.
After the annoucement, everyone knew that everyone knew that there is at least one with a read spot.
This extra information is leading to all n islanders with red spots leaving on the n-th day. (And all the ones with black spots on the day after.)

Again: wonderful puzzle.

[hyperpape]

@spongebob

What's confusing is what happens when there are three or more red spots--everyone already knows that everyone knows there is a red spot. You have to find a subtler way to characterize what they learn.

[SpongeBob]

@spongebob What's confusing is what happens when there are three or more red spots--everyone already knows that everyone knows there is a red spot. You have to find a subtler way to characterize what they learn.

If there are three red spots, then before the announcement, everyone knows that everyone knows there is a red spot. After the announcement, everyone knows that everyone knows that everyone knows there is a red spot.

[SpongeBob]

3 spots, BEFORE announcement:

Statement 1: everyone knows that everyone knows there is a red spot

black knows that everone knows there is a red spot
......black knows that black knows there is a red spot ... +
......black knows that red knows there is a red spot ..... +
red knows that everyone knows there is a red spot
......red knows that black knows there is a red spot ..... +
......red knows that red knows there is a red spot ....... +

-> Statement 1 is true.


Statement 2: everyone knows that everyone knows that everyone knows there is a red spot

black knows that everone knows that everyone knows there is a red spot
......black knows that black knows that everyone knows there is a red spot
............black knows that black knows that black knows there is a red spot ... +
............black knows that black knows that red knows there is a red spot ..... +
......black knows that red knows that everyone knows there is a red spot
............black knows that red knows that black knows there is a red spot ..... +
............black knows that red knows that red knows there is a red spot ....... +
red knows that everyone knows that everyone knows there is a red spot
......red knows that black knows that everyone knows there is a red spot
............red knows that black knows that black knows there is a red spot ..... +
............red knows that black knows that red knows there is a red spot ....... +
......red knows that red knows that everyone knows there is a red spot
............red knows that red knows that black knows there is a red spot ....... +
............red knows that red knows that red knows there is a red spot ..... -

-> Statement 2 is not true, some information is still missing and no one will leave the island.



3 spots, AFTER announcement:

With the announcement, statement 2 becomes true, information has been added.

[Redundant]

Spot

I think that a good way to characterize the new information is "If there were only one person with a red spot, that person would know that they had a red spot". Knowing this conditional is sufficient for the induction, and lacking without the proclamation of the visitor.

[SpongeBob]

Alright, next one. It might be already known to some of you, but still:

You are in a prision with two doors. One leads to freedom and one to death.

There is a guard before each door. You know that one always tells the truth and the other always lies and they both know it about each other, but you do not know which one is which.

You can adress one question to one of the guards. What do you ask to find out about the way to freedom?

[entropi]

Spot

I think that a good way to characterize the new information is "If there were only one person with a red spot, that person would know that they had a red spot". Knowing this conditional is sufficient for the induction, and lacking without the proclamation of the visitor.

But for starting the induction you need more. It is ok with one red spot but why should it also work when you add more red spots?

While I think SpongeBobs logic is correct, it should be possible to explain in a simpler way. Otherwise you should also have to show the same thing for 4 red spots, 5 red spots, ....

Here is my try using induction:
If there is just one red spot, it obviously works.

If there are two red spots, everyone already knows that there is at least one red spot.

But the next level of information comes from the observer (tourist), in the form of making each one of red spots expect the other to leave the next morning. Since the other one doesn't leave, he learns that there is one more red spot except that one.

So, every day he learns that there must be one more, and this information comes from the "expectation" (expectation that other red spots should leave) created by the observer.

So for creating the induction: When you add one more red spot, you delay the expectation of leaving one more day.

Without the observer, this expectation would never be created because there is no reason for any of the red spots to expect anyone to leave. Even if a red spot knows that N other red spots exist, there is still no information relating to the color of his own spot.

What the observer does is turning the rule of leaving next morning into information related to the number of red spots via the expectation.

[Redundant]

But for starting the induction you need more.

No. You don't. If there were one person, and this was known, he'd leave. If there were two, then after one day, the two people will know. It goes on. The knowledge of the conditional is sufficient.

Note that this is a conditional. The new knowledge isn't that there is at least one person with a spot, but that if there were only one that person would know.

[entropi]

But for starting the induction you need more.

No. You don't. If there were one person, and this was known, he'd leave. If there were two, then after one day, the two people will know. It goes on. The knowledge of the conditional is sufficient.

Note that this is a conditional. The new knowledge isn't that there is at least one person with a spot, but that if there were only one that person would know.

Maybe it is just a matter of definition, but for calling a proof "induction", you would need to prove (at least) two things:
1-It is true for x=1
2-If it is true for x=N, it is also true for x=N+1

In this case what you say is that the solution of the puzzle is true for 1 red spot. But it is not immediately apparent that if N red spots leave after N days, N+1 red spots would leave after N+1 days. Probably that is what you call "conditional". If it is, then we are saying the same thing.

I formulate it as "independently of the initial number of red spots, adding one more red spot would cause one more day of delay of the expected leaving day, because each additional red spot would add one more day of uncertainty (whether he would know or not) for all the rest of the red spots".

Anyway, the more I think about it the more I appreciate the puzzle, indeed wonderful.

[Redundant]

If we know that N red spots leave after N days, and we have N+1 spots.

Each of the people with red spots will see N people with red spots. If those N people don't leave after N days, on the (N+1)th day, each of these people will know they have red spots, and leave. As I'd say in about any homework assignment, "the induction is trivial".

I'm really not sure what we're disagreeing on here, now that I think about it.