Well, I guess it depends. Convincing yourself how it works isn't hard. Carefully stating the induction on number of red-spotted villagers or characterizing the change in their information each night seems like a royal pain in the butt.
Here's a harder one that originated with Raymond Smullyan:
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.
Re: Logical puzzles
Posted: Thu Nov 25, 2010 6:42 pm
by ethanb
hyperpape wrote:I'm going to say that one's not the hardest.
Well, I guess it depends. Convincing yourself how it works isn't hard. Carefully stating the induction on number of red-spotted villagers or characterizing the change in their information each night seems like a royal pain in the butt.
Here's a harder one that originated with Raymond Smullyan:
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.
Haven't worked out a total solution yet, but I have figured out how to make Truth's head blow up:
Ask all three of them the same question, while pointing at one of the others: "Would he say 'ja' if I asked him if the other god would say you were Random?"
False will answer "yes" unconditionally. Random is inscrutable in this regard. Truth will strike you with lightning.
EDIT: that's not necessarily a full solution for Truth either - if False is a literal-minded negative answerer, he may also have issues answering. My guess as to his answer depends on him being somewhat of a trickster and also somewhat antipathic toward Truth (and therefore might answer firmly but misleadingly rather than striking you with lightning ambiguously.)
Re: Logical puzzles
Posted: Fri Nov 26, 2010 7:48 am
by entropi
cyclops wrote:Both answers correct for the fuses problem. 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?
Wonderful puzzle. I could not solve it but at least understand the solution
Here is my favourite one:
There are 10 boxes full of golden coins. 9 of the boxes contain 100 gram coins, and one of them 110 gram coins. You are allowed to weigh only once for finding out which one of the boxes contains the 110 gram coins. (Note: By weighing I mean not comparing two (sets of) coins with each other but really measuring how many grams a (set of) coin(s) weighs.).
If you hear it for the first time it may not be so simple to solve. But once you know the solution it seems very very obvious, which is for me a good indication of a quality puzzle.
Re: Logical puzzles
Posted: Fri Nov 26, 2010 12:43 pm
by Gresil
Weighing:
Take 1 coin from the first box, 2 from the second etc. and measure the combined weight of these. If the first box has the heavier coins, the weight will be 1010 grams; if the second one has them, 1020 grams, etc.
Re: Logical puzzles
Posted: Fri Nov 26, 2010 5:04 pm
by entropi
Gresil wrote:Weighing:
Take 1 coin from the first box, 2 from the second etc. and measure the combined weight of these. If the first box has the heavier coins, the weight will be 1010 grams; if the second one has them, 1020 grams, etc.
the idea is correct But a minor correction: the total weight will be 5500+10N grams (N being the number of the box). 100+200+...+Nx110+...+1000
Re: Logical puzzles
Posted: Fri Nov 26, 2010 6:26 pm
by cyclops
hyperpape wrote: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.
Re: Logical puzzles
Posted: Fri Nov 26, 2010 7:44 pm
by hyperpape
@cyclops
cyclops wrote: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.
Re: Logical puzzles
Posted: Sat Nov 27, 2010 5:02 am
by SpongeBob
cyclops wrote:... 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.
Re: Logical puzzles
Posted: Sat Nov 27, 2010 6:30 am
by 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.
Re: Logical puzzles
Posted: Sat Nov 27, 2010 8:50 am
by cyclops
hyperpape wrote:@cyclops
cyclops wrote: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.
Re: Logical puzzles
Posted: Sat Nov 27, 2010 4:44 pm
by SpongeBob
SpongeBob wrote:
cyclops wrote:... 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.
Re: Logical puzzles
Posted: Sat Nov 27, 2010 5:56 pm
by 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.
Re: Logical puzzles
Posted: Sun Nov 28, 2010 6:22 am
by SpongeBob
hyperpape wrote:@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.
Re: Logical puzzles
Posted: Sun Nov 28, 2010 7:04 am
by 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.
Re: Logical puzzles
Posted: Sun Nov 28, 2010 9:44 am
by 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.
