You are a writer visiting a monastery.
“N” number of monks
At least one is infected with the plague
No communication what-so-ever
Only get together for 1 hour for lunch
Once you know you have the plague you have to kill yourself, you cannot kill others (you=monks, not the writer)
In how many days (in terms of N) will they get rid of the plague ?
Heres some additional info. There are N number of monks, and of which a certain amount are infected with the plague but the plague is not contagious so the number of infected and total number of monks N should only decrease. Another note is that if a monk is infected, he does not know. There are no ways for him to know if he is infected or not, he only knows if another monk is infected by a disctintive mark on the forehead. (Assume a monk cannot tell if he is infected because there are no mirrors of any sort, and other monks will not say).
As the writer, you can observe the N of monks everyday at lunch. You yourself cannot get the plague. I spent hours on this puzzle and I assume it falls under Game Theory. It is far too complex, and trust me guys, googling doesn’t help. All I know is that Days is a function of N.
What? There has to be more to this than what you’re providing. Under this set of rules, there is no way for a monk to know whether he has the plague, since neither the other monks nor the writer can tell him, and there are no mirrors. Therefore, the bit about killing yourself if you know you have the plague is irrelevant. Given that the plague is non-communicable, the answer would therefore be “whenever the last infected monk dies”. Days in this case would not be a function of anything, least of all N, because there is no rule from which to create a formula.
A minimum of two pieces of information are required for any sort of solution to this puzzle. The first would be the number of monks, either a definite number or a variable (which I will call Y), that are infected with the plague. The second would be a method of discovering that one has the plague. Perhaps the process for doing so is complicated, and requires action by multiple individuals over a period of time X. That would explain why the “1 hour together for lunch” is significant. Given that, we could calculate the probability of that action being performed during the lunch hour, and using calculus-based optimization, find the minimum occurences of (X) in which the probability would equal one that the required action would be completed for (Y) subset of (N), thereby coming up with an answer to the question.
Even given this information, the best we could come up with would be a three-variable function which you could use to calculate a minimum number of days (D) that would be required to get rid of the plague for any given values of (X), (Y) and (N). The question as you have phrased it, however, is meaningless.
This is based on the classic “Three Sages” puzzle.
The basic version is:
Now then. The problem clearly requires some defined interaction (the laughing at each other in the above problem). I believe the problem as it’s given is too vague. We know the fictional plague is non-infectious. Do the monks know? I.e. can we safely assume that monks will shun those with the mark? The problem is too vague.
Believe me, if I had additional relevant info, I woulda solved it myself. I am certain there is no way for a monk to know if he is infected. This sounds pretty stupid but this is an actual problem given by a college professor. I have heard that some students have spent many YEARS trying to solve it. I understand that under the current conditions, one most likely cannot reach a solution, but I was hoping that by posting this, someone out there might have seen the exact problem before.
You do need just a little bit more info. You need to know that all of the monks know all the information in the OP and follow all the rules and make all possible logical deductions and act accordingly. You also need to know that all of the monks know that all other monks know all this.
Also, N should be the number of monks that have plague, let the total number of monks be some M=>N. Notice that the time it takes for all plagued monks to kill themselves does not depend on M at all, but it depends only on the number of monks infected.
Now, here’s what happens:
First consider the case N=1 i.e. one monk with plague.
The monks come to eat lunch knowing that at least one of them has the plague. All other monks except for the infencted one see that some other monk has the plague and go about there business as usual. Now, the only monk with plague sees that no one else has the plague. Since he knows that at least one monk has the plague, he deduces that he is the one and kills himself.
Then the case N=2.
On the first day all monks see at least one other monk with the plague and no one kills himself.
Then on day two all monks see the same situation. Now, the two infected monks see that the only infected monk they saw on day 1 for some reason didn’t kill himself yet, so they deduce that the other monk must have seen someone else infected. Since they only see the other infected monk they deduce that they themselves must also have the plague and both kill themselves that night.
Now N=3.
All monks see at least two infected monks. Now, they have all deduced that if N was 2 both infected monks would have killed themselves after lunch 2, so if a monk still sees only 2 infected monks on lunch 3 they know that N must be larger than 2, meaning that they also have the plague and must thus kill themselves.
Other cases are similar and the infected monks always kill themselves on the same day after N lunches.
This is the sort of thing I was referring to as “an action which requires action by multiple individuals over a period of time X”. If we know that the monks will shun those with the mark, and we have either a specific amount or a range of time that it will take for a monk to notice said shunning, the problem becomes quite simple. We could complicate the problem a bit by making one out of every Z monks take pity on those with the mark and continue to associate with them, and so forth.
If this question, in the exact form you have stated, was actually given to college students by their professor, I rather suspect it was a test to see if any of them had the stones to firmly assert that it was impossible. I cannot see an intelligent student spending “years” trying to solve it.
This also makes the problem solvable, but a bit too easy. Given that the problem is presumed to be difficult, I would assume that the monks are unaware of the exact value of N. Of course, that’s little more than a WAG since I don’t think the problem was given as presented in the OP, and there is no way to deduce the exact nature of the missing information.
Of course they are unaware at first, they only know that N>0. However, when they see all the other monks and the distinctive marks on foreheads, they know that N must be the number of infected monks is that number or that number plus one if they have the plague themselves.
Actually, it doesn’t. What you read was a good explanation, but there are a few details I’d want firmed up if I wanted a rigorous proof. Besides, coming up with that answer is a lot more difficult than it was for you to just read it in a post.
Of course it was. I’m not trying to take anything away from PVirtanen for coming up with that. My only point was that I don’t see a group of reasonably bright math students taking overly long periods of time to figure that out. My fault for using the phrase “too easy”; I didn’t mean that the problem was easy, just that it wasn’t as hard as the OP made it out to be.
Furthermore, the problem as stated in the OP is in fact unsolvable without the additional given information PVirtanen included in his solution. I looked for the missing information from the wrong angle in an attempt to make the problem a mathematical one rather than one of logistics. Either PVirtanen has encountered this type of problem before, or is better at lateral thinking than I. In either case, I believe the details that you seem to dismiss as extraneous to be essential to the nature of the problem. That’s my only disagreement with what’s been said.
Oh, to be sure. To also be explicit, I’ll reiterate: The problem is not well-posed without the assumption that the monks all know the problem, are perfect logicians, and all know this information about each other. Since this sort of boilerplate is pretty much standard on this class of problems I figured it more likely that the OPer had omitted it, rather than that the professor had.
Why the heck is it called the plague if it’s non-contagious and why shoudl teh monks then kill themselves? But apart from that, I’m pretty sure this was meant to be a take-off on the 3 sages problem just with the number infected unknown so that ean monk must go through the added logical step that the number infected is either the number he sees or that plus one. – as has already been pointed out.
One problem with seemingly impossible problems where you think you have too little information to solve them is that if you don’t solve it, you don’t know what information is crucial to repeat and often subtle ideas that seem pointless (like all monks know all the info and know all monks know all the info) tend to get dropped in repeating.
And by the way even that isn’t quite enough. What we need is somethign called common knowledge in game theory. We need that
all monks know the info
all monks know that all monks know the info
all monks know that all monks know that all monks know the info
etc.
This is a rewording of a classic puzzle, except that the OP missed a couple of details. First, an infected monk will kill himself at midnight: This gives a certain required level of granularity to the problem. Second, when a monk dies, everybody knows about it (they scream loudly when they kill themselves). And third, on the first day, the visitor (who does not yet know the rules the monks follow) tells all of the monks “At least one of you has a mark on his forehead”.
Once you have this, PVirtanen’s solution works. To reiterate: If there is exactly one infected monk, he kills himself at the first midnight.
If there are exactly two infected monks, nothing happens the first night. Because nothing happens on the first night, all monks now know that there is more than one infected monk. So each of the infected monks sees only one forehead-mark among his fellows, and concludes he must be the other. So if there are exactly two infected monks, they both snuff on the second night.
If there are exactly three infected monks, nothing happens on the first two nights, so all monks now know that there are at least three infected monks. Any infected monk sees only two other infected monks, so he knows he must be the third, and each infected monk will suicide on the third night.
.
.
.
If there are exactly N infected monks, then nothing happens for the first (N-1) nights. If there were (N-1) or fewer infected monks, they would all have killed themselves already, so all monks know that there are at least N infected monks. Each infected monk looks around and sees only (N-1) other infected monks, so he knows he must be the Nth. So at midnight of the Nth night, all N infected monks commit hari-kari.
Just to clear some things up. Yes the monks are aware of the fact that a plague is going around, and a mark on the forehead means one is infected. At least one monk is infected as stated in the problem, which I’ll call X (infected monks) > 0.
It is obvious when a monk has killed himself because each day when they all meet for lunch, the number of monks N, will decrease if a monk(s) has died.
There is absolutely no form of communication between the monks, directly or indirecty. For instance, a monk who see another monk having the plague cannot and does not make a facial gesture, any form of ostacizing infected monks is also impossible. In short, a monk who is infected cannot determine if he is infected based on the behaviour of other monks. No communication.
I assume the “you are a writer” is significant because you cannot have the plague, you’re simply observing the monks N when they have lunch each day.
To the poster who says that D = n^0, I am curious as to your conclusion as you are basically stating that D is 1. I am quite eager to solve this and rid the headaches it has caused. Maybe you could post the explanation under a spoiler warning so those who wish to still work on the problem may do so.
My appologies to the OP. I based my solution on the premise that the plague was extremely contagious having overlooked your additional info . Even so on reflection I can’t understand how I even came up with the “answer”. I must have had a senior moment.