Author |
Topic: Island of rabid dogs (Read 6865 times) |
|
Samual Dollar
Guest
|
I found this riddle from another forum which is supposed to have been from a microsoft interview and have been stumped on it for awhile, I hope some of you can figure it out before I go out of my mind 
"There are 99 dogs on an island. The owner of the dogs are standing next to them. Each owner can not see each other clearly but they know that the other owners are there. 16 of the dogs are rabid. Only the owner can kill his dog, but for that owner to kill the dog they must be 100% sure that their dog is rabid because of emotional ties to their dog. each of the owners know that at least 1 dog on the island is rabid. It is crucial for the survival of those on the island to find all 16 dogs and kill them. All killings take place at midnight, and there can be any number of killings per night. How many days will it take to find /kill all the dogs? and how did you come up with the answer?
hints:
each owner can not see the other owner's expressions nor dog's expressions, it is as if there is a forcefield around each owner hindering distinct vision of that owner.
think logical"
If you can figure this out you can be a software programmer at microsoft. Btw, the fastest someone has figured out the answer has been reported to be 3 mins, avg is 3hrs-never. Good luck.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
 |
Re: Island of rabid dogs
« Reply #1 on: Jan 12th, 2005, 10:04am » |
 Quote  Modify
|
I don't think this question has been stated properly.
Clearly the intend must be equivalent to the red eye monks puzzle, or the muddy children or countless variants of the same thing.
Here, however, there are a few problem.
Do the owners know if their dog is rabid? If so, they could kill it immediately not leaving much of a puzzle.
But then they should at least know whether the dog of another owner is or isn't rabid.
Even so, simply knowing there is at least one rabid dog won't set of the chain of events necessary to resolve this, unless there is only one (in which case the owner knows it's not any of the other owners' dogs, so it must be his)
Or we could simply take the dogs to the vet and get test results.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Samual DOllar
Guest
|
|
Re: Island of rabid dogs
« Reply #2 on: Jan 12th, 2005, 10:23am » |
Quote Modify
 Remove
|
Well, The person who posted it said there is a vry simple logical solution to this, so I'll post it when he gives it out.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Island of rabid dogs
« Reply #3 on: Jan 12th, 2005, 4:25pm » |
Quote Modify
|
towr's point is that the puzzle is mistated. As you have stated it here, there is:
1) No statements applying to the question of what each owner knows about the state of his own dog.
2) No statements as to what owners may know about other dogs.
Both of these are needed to provide the solution but have some how been dropped from this version. As I agree with towr that this is the Red-eyed Monks puzzle (see the Medium section) in another form, I am sure that the following conditions were meant to be included:
1) Each owner does not know the state of his own dog, nor is he able (for emotional reasons) to determine the state himself.
2) Each owner DOES know the state of everyone else's dogs.
3) Fact (2) is known to every owner (i.e., every owner knows that every owner knows the states of every other owner's dogs).
4) The owners do not know how many dogs are rabid (only we solving the puzzle are privy to this information).
5) At some point, all the owners are made aware on the same day that there is at least one rabid dog on the island.
6) (5) happens in such a way that every owner is now aware that all other owners are aware of this fact.
7) All owners are aware each day of whether any of the other owners have killed their dogs the previous midnight.
8) (A standard assumption) Everyone is sufficiently intelligent to deduce everything needed.
Under these conditions, on the 16th midnight after the announcement of a rabid dog, all the owners of rabid dogs will kill their dog. To understand why, go read the Red-eyed/brown-eyed Monks thread in the Medium forum.
|
| « Last Edit: Sep 6th, 2005, 6:33pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
L'Vanctz Swain
Guest
|
It should take them only one night to kill all the dogs that ae rabid. Even If all the owners can't see each other the should at least be able to tell if their dog is rabid or not.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Island of rabid dogs
« Reply #5 on: Sep 6th, 2005, 6:33pm » |
Quote Modify
|
Note my condition (1) from the post above. The way this riddle works, it needs to be set up so that each owner does not know the state of his own dog, nor can he determine the state himself. He can only discover the state of his dog by deduction.
Without condition (1) (and the other conditions), the whole thing is trivial.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Island of rabid dogs
« Reply #6 on: Sep 7th, 2005, 5:21am » |
Quote Modify
|
Condition (9) : every owner must kill his dog at midnight as soon as he knows his dog is rabid. And it happens in such a way that the others don't hear it (is that the "forcefield" Samual spoke about?).
(still assuming the "red-eye monks" problem was what was meant)
|
| « Last Edit: Sep 7th, 2005, 5:23am by Grimbal » |
IP Logged |
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: Island of rabid dogs
« Reply #7 on: Sep 7th, 2005, 2:17pm » |
Quote Modify
|
on Sep 7th, 2005, 5:21am, Grimbal wrote:
And it happens in such a way that the others don't hear it .
|
|
Hahh?
I thought it was vital for everyone to hear it... otherwise there would be no stop condition, and it will end with everyone killing their dogs...
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Island of rabid dogs
« Reply #8 on: Sep 8th, 2005, 7:27am » |
Quote Modify
|
I mean, if the dogs would get shot and if at midnight you don't hear the shooting, you might already deduce your dog is rabid and shoot it while it is "still midnight".
They have to discover the fact the next day. This is the way it was in the problem with the unfaithful husbands.
Or maybe that was meant with the idea that they don't see each other. One night at midnight they hear the dogs being shot. And you know you won't need to kill yours the next night.
I wonder if the confusing way the problem is set is not on purpose. You probably learn much more about people's problem solving abilities if they first have to get the problem straight than if they can just give the solution they might have read somewhere without really understanding it.
|
|
IP Logged |
|
|
|
fireashwinter
Newbie
Posts: 7
|
|
Re: Island of rabid dogs
« Reply #9 on: May 19th, 2006, 12:57pm » |
Quote Modify
|
I'm assuming anyone still cares:
Each of the 83 owners of healthy dogs "knows" of 16 definitely rabid dogs and 82 definitely safe dogs, and "suspects" 1 rabid dog (his own).
Each of the 16 owers of healthy dogs "knows" of 83 definitely safe dogs and 15 definitely rabid dogs, and "suspects" 1 rabid dog (his own).
The information drops in that "at least one dog is rabid." Other than that, no owner is precisely sure what the other owners "know."
If an owner were aware of 98 non-rabid dogs, that would force his own to be rabid, so he would have to kill it that first midnight. But that is not the case. If there were 2 non-rabid dogs, each owner of a rabid dog would "know" about 1 already, so would wait the first night. That much is "obvious."
The discussion of the difference in "awareness" explains what puzzles so many people-- why is there a limit on the killings?
If an owner is aware of 97 non-rabid dogs, 1 rabid dog, and possibly his own, on that second night, that owner knows that there are at least 2 rabid dogs. Since that owner is aware of 2 rabid dogs, and 97 normal dogs, the total being 99, he knows his dog is rabid and must kill it.
If an owner is aware of 96 non-rabid dogs, 2 rabid dogs, and possibly his own, on that second night the "information" he has is nothing new to him: the "info" is that at least 2 dogs are rabid, and maybe his own, but he already knew that. So, that owner does nothing on that second night, because he has not much "new" to act on and the game ends before his dog is in jeopardy.
Similarly, the owners of "safe" dogs on that 16th midnight were already aware of the possibility that their dog was rabid, so they are waiting one more night to see if the total of "rabid" dogs must increase past 16. The owners of the "rabid" dogs on that 16th night know that one more dog than the 15 they were aware of is "rabid," so that dog must be theirs (as they were aware of all the others). The execution occurs that night, the game ends that night, the rabid dogs die and the safe dogs, for the time being, survive.
The "checks" that are needed are the assumptions that no dog dies other than by execution, that owners are aware of the state of other dogs (therefore condition as rabid or as dead), and executions occur on and only on 100% certainty.
Oh, and it also requires the assumption that any group of people on an island could collectively realize all of this, but it's all theoretical anyway (which is why IMHO one shouldn't even have to point out the "ideal" rules, such as no random deaths or killings-- it's already understood to be "ideal").
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Island of rabid dogs
« Reply #10 on: May 19th, 2006, 4:00pm » |
Quote Modify
|
The reason this puzzle never had a solution posted was because we "solved" this puzzle by noting that it was a pre-existing puzzle in another form, at least when corrected. So all of our posts were about how to correct the puzzle so that it was actually solvable, and not trivial, rather than repeating a solution we were already familiar with.
If you haven't already, I suggest reading the Red Eyes Brown Eyes thread. The riddle itself is found on the main riddle page: Brown Eyes and Red Eyes.
It is apparent that you already know the solution, but there is some very interesting discussion none-the-less. Particularly after Chronos posted some variations on the original question a few pages in.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
graphia
Full Member
Gender:
Posts: 202
|
|
Re: Island of rabid dogs
« Reply #11 on: Jun 19th, 2006, 3:01am » |
Quote Modify
|
Oh and just to be a clever prick...since the rabies virus can be incubated for up to two years before showing symptoms there is no way of telling whether the dogs have it or not short of taking it to a vet, who would put it down anyway - since all the dogs are in close proximity and have been for some time while their owners puzzle it out, the only safe answer is to quarantine the island, shoot *all* the dogs and keep their owners also under quarantine while blood tests are performed and vaccinations administered
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print