From - Fri Sep 4 22:18:15 1998
From: Walter Baeck
Newsgroups: sci.math
Subject: A Recursion Problem
Date: Fri, 04 Sep 1998 18:39:19 +0200
Organization: ALCATEL BELL
Lines: 175
Message-ID: <35F017B7.5FF6@sh.bel.alcatel.be>
8 years ago I was given the following puzzle:
There is an abbey of monks living under very severe rules.
They meditate during most of the day in strict isolation,
in absence of any luxury at all. The only moment when they
meet each other, is for the evening meal. There is a strict
prohobition to speak to each other, or communicate any other way.
One day the chief of the convent announces at the evening meal
that there has been an outbreak of a contagious disease.
The effects of the disease are not noticeable to the patient
during a long time of incubation, because there is no pain at all.
However, it is very visible to others because the sufferer gets,
say, green pimples in the face. The abbot asks that the sick
leave the abbey as soon as possible. The only moment of the day
when the sick are allowed to depart, is after the evening meal.
Of course the problem is that nobody knows if he should leave or not.
No one knows if he is ill himself, because other people can't tell;
and there is no possibility to see a reflection in mirrors or any
other objects of luxury. However, everyone can see very clearly
at the evening meal, which other members are ill.
Moreover, they have endless time on their hands to think about a
correct algorithm all day long in their room.
How do the right group of people decide to leave ?
******************************
******** ********
**** ****
** **
* *
* DON'T READ ON IF YOU WANT TO THINK ABOUT IT YOURSELF *
* *
** **
**** ****
******** ********
******************************
Let's assume that only one monk is sick. The problem becomes trivial,
if you look at it from that one monk's point of view. He sees only
healthy people around him. Nevertheless the abbot wouldn't be lying,
would he? Therefore he knows that *someone* must be ill; the only
possible explanation is that he himself is the only ill person.
He leaves on the first day after the meal.
Then we move on to the situation with two sick monks. They see the
other sick guy at the table, and assume that he will be in the position
described just above. So he's gonna notice in surprise that the other
guy *doesn't* leave after the first day. The other guy will be equally
surprised of course, because he had expected the first one to leave
after the first day. These guys draw the only logical conclusion:
"The other guy must have thought that someone else surely would leave.
I see no-one else sick around, so *I* must be the one that he assumed
to be leaving." So the 2nd day, the both leave together and the affair
is settled.
All you mathematical geniuses out there sure know where this is leading,
but let's do one more for a clear understanding. Three sick monks!
Each of these three sees two other pimple-faces at the table. During
their endless contemplations, they have of course considered the
situation
with two ill people. So they recognise the case of the "2-ill conflict"
and they realise that it's gonna take 1 day before these two have
resolved their confusion (as explained above). The shock will be all the
worse when at the 2nd meal, those 2 monks *don't* leave. Once again,
there is only one logical explanation: "There must be another sick
person
around. However, I see none, so it must be me." All three sick monks
realise this after the meal on the 2nd day... and all three of them
leave on the third day.
The general solution will be, that n sick monks notice on day n-1 that
the n-1 visible sick monks are not leaving, and therefore realise that
they are sick themselves. All n of them leave on the next day (= day n).
------------------------------------------------------------------
I've always found this a very beautiful example of recursion.
People who are not mathematically educated can also appreciate
the elegance of it, when the solution is explained to them.
Normally when people are presented with the theoretical concept
of recursion, the same boring examples of Fibonacci series, or n!
calculations, are given. But this problem could do equally well.
I've forgot about this puzzle since quite a while now.
This week when I was reading in Barbara Tuchmans "A distant mirror:
The Calamitous 14th century", I encountered the chapter about the
Plague. It made me think of that riddle again.
I've become an engineer in the meantime, and now I'm not only interested
in mathematical elegance, but also in optimisation.
When reconsidering this puzzle, I started wondering if this is really
a recursive problem after all.
It looks so silly that, when 9 monks are ill for example, everyone
has to sit around and wait for 8 days to pass, before the ultimate
moment has really come. Everyone in the abbey, ill or healthy, will
realise
that with the recursive solution, nothing is going to happen for quite
a few days. The real moment of truth is day 8, when the healthy people
are still relaxed (they only worry about what will happen on day 9)
but the sick people are concerned to see if the other 8 sick guys
will be leaving. Before that day, no real information is conveyed.
It would be more efficient to have that moment of truth immediately
on the first evening. All the waiting time before that, can be skipped.
Of course, the core of the problem is precisely that nobody knows
exactly what n is. Therefore they don't know n-1 either, so they don't
know how many days should be considered as skipped.
HOWEVER... everyone can only be off-by-1 in their estimate of 1.
The healthy people see 9 rashed monks around them, so they know n is
going to be either 9 or 10. The sick people see 8 pimple-faces at meal,
so they know n is 8 or 9. There should be a way of having everyone
decide on a number of waiting days to be skipped, that works correctly
for healthy as well as ill people.
I propose a solution like "when the n could be either k or k+1, take
the largest odd number strictly smaller than k as the days to be
skipped".
The inequality has to be strict, because otherwise one of both groups
is going to pick a too large number of days to be skipped. The fact
of even or odd choice, is just a matter of convention; basically its
function is to reduce the uncertainty of 1 day margin, to certainty.
With odd choice, in our example the number of days to be skipped would
be
7. Therefore, they consider the first evening as the 8th evening of the
recursive solution. This happens to be the decisive moment: all 9 sick
monks see that the other 8 visible sick monks are not leaving on the
so-considered 8 evening; they all leave the next day.
In case an even number of days would be chosen, this would be 6 in the
example. The first evening would be the "7th day". The next day would
be the 8th day, or the moment of truth; and on the 3rd day the sick
would go.
In the quest for optimisation, the smallest cases for n should be
considered
for the even/odd decision. n=1 is trivial and cannot be optimised by any
skipping. n=2 wouldn't be helped either.
For n=3,the 3 sick guys consider possibilities 2 or 3;the rest thinks 3
or 4.
To have some gain, not 0 should be the outcome, but 1; therefore the
number
of waiting days to be skipped should be odd.
Any comments on all of this?
____________
\ / Walter Baeck
\ ALCATEL/ Alcatel Telecom
\ BELL / Switching Systems Division
\ / Microelectronics Design
\ / E-mail : baeckw@sh.bel.alcatel.be
\/ Phone : +32 3 240 73 86
I guess a 20th-century variant on this puzzle would go like:
"David Koresh comes busting in and yells: Yo gang, you shouldn't have
taken this Solar Temple thang too literally. You weren't meant to
_sleep_
under sunbeds actually. Some of you face an unpleasant face now.
Get these skin cancer cases out of here A.S.A.P. !!
Will the affected cult members please step outside and set fire to
themselves ? Burning stuff is Cool, so just relax and go with it.
Only time for burning is at noon.
.. and the sect went to sit in front of their keyboards all day long.
They put thousands of possible algorithms through a simulation, and
Computer decided on the optimal choice. On the third noon by the
latest,
the diseased went out in flames... "