wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> microsoft >> Island of rabid dogs
        
(Message started by: Samual Dollar on Jan 12^th, 2005, 9:12am)

Title: Island of rabid dogs
Post by Samual Dollar on Jan 12^th, 2005, 9:12am

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.

Title: Re: Island of rabid dogs
Post by towr on Jan 12^th, 2005, 10:04am

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.

Title: Re: Island of rabid dogs
Post by Samual DOllar on Jan 12^th, 2005, 10:23am

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.

Title: Re: Island of rabid dogs
Post by Icarus on Jan 12^th, 2005, 4:25pm

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.

Title: Re: Island of rabid dogs
Post by L'Vanctz Swain on Sep 6^th, 2005, 5:33am

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.

Title: Re: Island of rabid dogs
Post by Icarus on Sep 6^th, 2005, 6:33pm

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.

Title: Re: Island of rabid dogs
Post by Grimbal on Sep 7^th, 2005, 5:21am

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)

Title: Re: Island of rabid dogs
Post by BNC on Sep 7^th, 2005, 2:17pm

on 09/07/05 at 05:21:41, 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...

Title: Re: Island of rabid dogs
Post by Grimbal on Sep 8^th, 2005, 7:27am

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.

Title: Re: Island of rabid dogs
Post by fireashwinter on May 19^th, 2006, 12:57pm

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

Title: Re: Island of rabid dogs
Post by Icarus on May 19^th, 2006, 4:00pm

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 (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1027806383) thread. The riddle itself is found on the main riddle page: Brown Eyes and Red Eyes (http://www.ocf.berkeley.edu/~wwu/riddles/medium.shtml#brownEyesRedEyes).

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.

Title: Re: Island of rabid dogs
Post by graphia on Jun 19^th, 2006, 3:01am

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 ;)