Saturday, July 21, 2012

GeekDad Puzzle of the Week: Dog Siblings

Black Labs, mrpattersonsir@flickrGeekDad Puzzle of the Week: Dog Siblings:
Q: A guy with a black lab said that his dog, Selkie, has five brothers and sisters in town. "But I’ve never run into one of them," he said. "I wonder what are the chances of that?"

Imagine that each of the six dogs goes out somewhere an average of once every three days. And imagine that between trails and parks and fields there are 200 places a dog can go, all (let's say...) with equal probability.

If it's been exactly two years — 730 days — since Selkie's owner picked her up from the litter, what are the chances that during this time Selkie would NOT see a doggie sibling?
For extra credit, what are the chances over the same time that any sibling will meet any other sibling?
I've got my answers which I will reveal after the deadline. In the meantime, feel free to solve it and submit your answer to GeekDad.

Edit:  The deadline was Friday, so here is how I went about solving the puzzle.

The key to this puzzle is figure out the chances of dogs not meeting on one day.  From there it is easy to figure out the chance of them not meeting for 730 days. And then if necessary, you can figure out the probability of the opposite case (meeting) by subtracting from 100%.

Part 1 - Selkie doesn't meet a doggie sibling

In order for a dog to be at a specific location, they must be out (with 1/3 probability) and at that specific spot (1/200 probability). That means there is a 1/600 chance of a specific dog being out at a specific location.  Thinking of the negative probability, that means there is a 599/600 chance that a dog is *not* at a specific location.

Selkie will *not* meet another dog on a specific day if,
1) Selkie is at home (2/3)
2) Selkie is out at any location (1/3) and dog 1 is not there (599/600) and dog 2 is not there (599/600) and dog 3 is not there...

In other words, the chance that Selkie doesn't meet any other dog on a specific day is:
2/3 + 1/3 x (599/600)^5 ≈ 99.7231466062%

And the chance that Selkie doesn't meet any dogs for 2 years (730 days) is:
[ 2/3 + 1/3 x (599/600)^5 ]^730 ≈ 13.2148023616%

A: (Part 1) The chance that Selkie does NOT see a doggie sibling is around 13.2148%

Part 2 - Chances that any sibling meets another sibling

This is the much tougher question.  First let's make a table of probabilities of having 0 dogs out, 1 dog out, 2 dogs out, etc.

The chance that 'n' dogs are out on any one day is C(6,n) x (1/3)^n x (2/3)^(6-n).
And given 'n' dogs are out, the chance that they do NOT meet is 200/200 x 199/200 x 198/200 ... (using the number of dogs that are out.)

Thus, the chance that no dogs meet on a single day is around 99.1717389885%
The chance that no dogs meet for 730 days is (99.1717389885%)^730 ≈ 0.2307745729%
Subtracting from 100%, you get the probability that at least two siblings will meet (100% - 0.230774573%) = 99.769225427%

A: (Part 2) The chance that any of the siblings meet during those 2 years is around 99.7692%

1 comment:

For NPR puzzle posts, don't post the answer or any hints that could lead to the answer before the deadline (usually Thursday at 3pm ET). If you know the answer, submit it to NPR, but don't give it away here.

You may provide indirect hints to the answer to show you know it, but make sure they don't assist with solving. You can openly discuss your hints and the answer after the deadline. Thank you.