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... "