Alice in Wonderland

[ZFR]

Wow, I haven't logged in ages. Just accidentally stumbled upon the forum today.

Anyway, here is a very interesting one I found in my native language. I tried to figure it out in almost an hour, and was actually just about to click "search" in google for the answer when it struck me. I hope my English translation is good, it's really clever.

-----

As Alice was walking along a path in one of the Wonderland forests, she heard some noises coming from behind a group of trees. Being a curious person, she climbed one of the trees. As she reached the top, she saw a curious scene.
31 people were sitting around a giant table. In front of them stood a little man with a short white beard, dressed in a scarlet tunic. He gestured for silence and began one of the strangest speeches that Alice has ever heard.

"Greetings fellow logicians. We, the Masters of Logic, the best of the best minds in Wonderland are gathered here today at our 125th annual convention. We are gonig to discuss matters of logic, swap tales of our brilliance, and talk about things incomprehensible to mere mortals.
Before we start however, let us play a little game..."
Here, the Speaker went around the table, and using one of the many coloured markers he was carrying, he drew a large dot on each person's forehead. After finishing, he began explaining the rules of his strange game.
"As you can see, each of you can see dots on the foreheads of all of his colleagues. But I was careful that no one noticed the colour of his own dot. The task of each one of you is to find out the colour of the dot on his forehead.
There is only one rule and it is a simple one. Every minute a bell will sound. If, at the time of the bell any one of you already knows the colour of his dot, he is to get up and join me under that tree, where I'll be sitting. Those who still don't know the colour of their dots, must remain at the table.
Remeber: If you know the colour of your dot, you *MUST* get up and come to me, and if you don't know it, you *MUST* remain sitting. Of course, being masters of logic and possessing such great minds, I'm sure that none of you will make a mistake. One more thing: you may not communicate with each other in any way. And as you can all see, there are no mirrors here or any reflective surfaces that would allow you to see your own dot and give you an advantage."
At this moment, Little Johnny, the youngest of the group, interrupted him and asked: "But professor, are you sure that we'll be able to solve this task?"
"Do not worry, young man," the Professor replied calmly. "It is possible to solve this task."
The youngeter smiled contentedly and sat down. He, and everyone else present, knew that the Professor could not utter false statements.
At this point, the Professor left the table, and went to sit under the tree, and Alice watched with amazement as the game began.
When the first bell sounded, four people stood up and left the table to join the Professor. At the second bell, some more people left the table, all of them having red dots. At the third bell, no one left the table, but at the fourth, at least one person got up. At this point in the game, Little Johnny and his sister (who had a different coloured dot than him) were still sitting at the table. But they were both sitting under the tree with the professor before the last bell sounded.
So the question is: How many times did the bell ring before all of the logicians left the table?

[Brian-E]

This type of logic puzzle always intrigues me. I'm not getting anywhere with it yet, though.

I think:
that the information that the task is solvable must constrain what coloured dots the Professor has drawn (because in general the task would not be soluble), so that information coupled with the sight of the dots around then will have been used by the four people who joined the professor on the first bell.

Now I need to puzzle further.

[TimSorbet]

I'm guessing it was on the sixth ring that the last two left the table. This puzzle sounds similar to the blue eyes puzzle (see [URL="http://xkcd.com/blue_eyes.html"]puzzle[/URL] and [URL="http://xkcd.com/solution.html"]solution[/URL]). So, without bothering to figure out all the details of the events of ring 1-4, I'm guessing that since there are only two people remaining at the fourth bell, they will (like the islanders in the blue eyes puzzle, and for the same reason) wait two rings, and get up on the sixth.

[ZFR]

Originally Posted by Mini-Geek

I'm guessing it was on the sixth ring that the last two left the table. This puzzle sounds similar to the blue eyes puzzle (see [URL="http://xkcd.com/blue_eyes.html"]puzzle[/URL] and [URL="http://xkcd.com/solution.html"]solution[/URL]). So, without bothering to figure out all the details of the events of ring 1-4, I'm guessing that since there are only two people remaining at the fourth bell, they will (like the islanders in the blue eyes puzzle, and for the same reason) wait two rings, and get up on the sixth.

Mini-Geek:
The puzzle doesn't say that there were only 2 people. Johnny and his sister were there. There may or may not have been more.

Brian-E:
Your approach is correct.

EDIT:
I just read the blue eye puzzle and it is indeed "similar" in a broad sense. So don't read its solution if you don't want a spoiler for this one. If you already know the answer to that one, you probably can figure out this one.

[Mr. P-1]

I do not believe the problem is solvable as written. Perhaps there is some additional information available to the particpants lost in the translation - perhaps that every marker was used at least once?

[Mr. P-1]

Originally Posted by Mr. P-1

...perhaps that every marker was used at least once?

With this stipulation, each of the participants can solve the xkcd problem simultaneously for each dot colour. At the first bell, those with a unique dot colour (four in total) leave the table. There are exactly two with red dots, and no dot colour is present exactly three times. A multiple of four people leave on the fourth round.

At this point there are 5, 9, 13, 17, or 21 people left. Moreover, each colour is present at least five times. There cannot be 5 or 9 people because then Johnny and his sister would have to have the same colour.

I cannot see how to determine between the remaining possibilities. The worst case is that there are two colours remaining, one on 5 fourheads, the other on 16. In this case it will take 16 rounds total for everyone to be under the tree. But it might take less.

[ZFR]

Mr. P-1, you're on the right track, but you got some things wrong.
Just to clarify, no critical info was lost in translation. I was only concerned that the translation would not make a good story or that it would make the puzzle sound "silly", but all the logical information needed to solve it is there.

We don't know if each marker was used only once. In fact, none of the people could see what markers he used and how many he had.

Read Brain-E's post! That, together with what you came up with, should give you the solution.

[Mr. P-1]

Originally Posted by ZFR

Read Brain-E's post! That, together with what you came up with, should give you the solution.

It doesn't. I considered it carefully and cannot see how it helps.

There are two logic problems here: The one posted to the 31 logicians, and the one posed to us. The statement that the problem faced by the 31 logicians is solvable by them, is potentially useful information to us (who have less information than they do), but it cannot help the logicians themselves: If the problem is solvable by them, then they can solve it without being told that they can. On the other hand, if the problem (without that additional statement) is not solvable by them, then the statement is simply false.

I cannot see how any choice of dot colours would enable any of the participants to deduce anything with the information provided: Suppose there is. Let C be such a configuration and let Fred be the name of one of the four who moves to the tree at the first bell. Then C can be replaced by a different configuration C' identical to C except that Fred's colour is different. The information available to Fred is identical in the two cases, so Fred cannot distinguish between them. Therefore Fred cannot move to the tree at the first bell. Contradiction.

Edit: Despite the above, I think I may now have a solution. Working out the details...

[Mr. P-1]

Originally Posted by Mr. P-1

Edit: Despite the above, I think I may now have a solution. Working out the details...

Assume that nobody sees any marker that isn't used on someone else, i.e., that the set of coloured dots on every other participant's forehead is the totality of colour information that any participant has.

Each participant can deduce as follows: Can my colour be different from every other colour I can see? If so, then the problem is insolvable. Therefore my colour must be one of the colours I can see. S/he can then reason as above, but starting at round 2. as follows:

Two different colours are present each on exactly two people. These four get up at the first bell. There are three people with red dots, who leave on the second. None leave on the third. A multiple of 5 leave on the fourth.

This leaves 9, 14 or 19 participants. 9 would leave Johnny and his sister with the same colour. If there are 14, then the colours could split 6-8 or 7-7. Either way, the game ends on bell 6 (in the case of 6-8 split six would leave on bell 5, the rest could deduce that they all had the same colour and leave on round 6)

19 participants could split 6-6-7, ending the game on bell 6. Or it could split two ways, the worst case being 9-10, ending the game on bell 9. I still don't see how to narrow this down any further.

[ZFR]

Your solution is correct Mr. P-1. Well done!

Just a minor detail on how to narrow this down further: the last sentence says "they were both sitting under the tree with the professor before the last bell sounded."


This would mean that when they were sitting with the professor, there were still some people left at the table.
So there couldn't be 14 participants left. If there were, the split would be either 6-8 or 7-7 as you said, but either way Johhny would be in one group, his sister in another and none would be left on the table after they both leave.
So there had to be 19 left. The only combination possible is 6-6-7.

[Mr. P-1]

Originally Posted by ZFR

Your solution is correct Mr. P-1. Well done!

I'm afraid I have to disagree with you. I just wanted to confirm that this solution was the one you were expecting.

The problem is that "If my colour is different from any other I can see, then the problem is insolvable. Therefore my colour must be one of the colours I can see". is no more cogent than any other argument of the form "if my colour is different from <foo> then the problem is insovable. Therefore my colour must be <foo>. For example: "If my colour isn't my favourite, then the problem is insolvable. Therefore my colour must be my favourite." or "If my colour isn't the same as my shirt, then the problem is insolvable, therefore the colour must be same as my shirt".

That the original version of the argument seems natural while the others seem contrived has no bearing upon their validity. The issue here is that the problem as stated is insolvable. Simply saying that it is solvable doesn't make it so.

If they logicians "solved" it in the way I described, then they did so by making an invalid inference.

Just a minor detail on how to narrow this down further: the last sentence says "they were both sitting under the tree with the professor before the last bell sounded."

Quibble: There is nothing in the problem as stated that says that the bell did not ring again, after the last of the people left the table. So it's possible that Johnny or his sister were in the very last batch.