Sunday, February 24, 2008

Nyet's Brain Echo, Vol. 2

Another classic:
Ten exceptionally logical and pious monks live in a monastery where it is strictly forbidden to speak (especially about one's appearance) or look in mirrors/reflections. The monks go about their daily routine and each night meet for supper, where all of the monks can see one another, but none can see himself. One night, the voice of God appears to all of the monks in a dream and states, "At least one of you will receive a blue mark on your forehead tonight. If you determine at any dinner in the next two weeks that you have a mark, you are to leave the monastery that night at midnight, never to return." Eight of the ten monks receive marks. How many days does it take the eight monks to leave the monastery?
Ready? The answer, as gained from Mathland, is eight days, arrived at via inductive reasoning. Say there were only one monk: he would show up at dinner that night, see nine monks sans marks, and deduce that he must be the marked monk. All of the other monks would see the monk with a mark and think "either there is only one marked monk and that guy is it, or there are two and I am the other one." They wouldn't be sure whether they had a mark or not, so they wouldn't leave, but when the monk was missing the next night, they would realize that he must have been the only one. In the case where there are two monks, on the first night each of the two marked ones would see one other marked monk and, as above, deduce that either there is one or there are two and he is the second one. The unmarked monks would see two marked monks and note that there are either two or three. No one would leave after the first night, but on the second night, the two marked monks would realize that the other was not alone, and so they would leave that night. Again, on the third night, the two marked guys would be gone, so everyone else would realize they were unmarked. This same effect - similar to the previous post's exam example, actually - continues if there are three, four, five, etc., monks each time, and the marked monks leave on the corresponding (third, fourth, fifth, etc.) night. Quickly:

Case of three:
Marked see two others, know there are two or three.
Unmarked see three, know there are three or four.
After first night, marked are still waiting to see if the two person scenario plays out.
After second night, when two person scenario doesn't play out, the three realize there are three, and leave on the third night.
At next dinner, there are only seven left, and they all realize they must be unmarked.

Of course, the thing that is severely counterintuitive about this is that the logic would apply if we had 1000 monks and 998 of them were marked. They would seemingly sit around for 998 days before anyone left??!?!?

Weird. And weirder, this all theoretically hinges on the idea of "common knowledge," in that knowing at least one person is marked and knowing everyone else knows this is the key. Notice that in any of these scenarios, the action doesn't take place until the minimum number of marked monks becomes universally agreed upon.

Anyways, ponder, comment, talk about milkshakes and then smack a monk with a bowling pin. Whatever; your call.

No comments:

Post a Comment