Farmer Brown lives in a land where farms stretch far and wide. One day he wins the lottery and wants to tell his neighbors. He tells his nearest neighbor of his good fortune. What follows is an odd sort of transmission of the news: each person who hears it (as well as farmer Brown himself) tells only his nearest neighbor, no one else.
Whenever that nearest neighbor is the person who told him the news, that branch of the transmission is closed, as there's no point in telling the person who told you, and there's no substitution of the second nearest neighbor.
-
What's the probability that the only person to get the news is the one farmer Brown called himself, due to farmer Brown being his nearest neighbor's nearest neighbor?
-
What's the expected number of people, besides farmer Brown, who will get the news before the transmission dies out altogether?
Consider the land where this happens an infinite plane, with each farmer a randomly placed point with uniform probability density.
I'm just going to call the neighbors points, per the last sentence. Here are some random thoughts from poking around at the problem.
Some pairs of points will be mutually closest neighbors (A and B) and each score 1.
Some points may be part of a chain ...D,C,B,A where C is the closest point to D, but B is the closest to C, and A is closest to be. The scores along this chain would be ...3,2,1,1.
It's not enough to identify these chains since they are actually trees with another point X having C as it's closest without and also scoring 3.
For finite collections of points we can give a min and max average.
If n is even the points could all be in mutual pairs all scoring 1 and averaging 1.
If the n points are in a single chain. The total score would be n(n-1)/2+1 which gives an average (n^2-n+2)/(2n).
A couple of hand plotted simulations (with n=10) gave averages of 1.2 & 1.8. I didn't feel like doing more.
This problem is given in two dimensions. In different numbers of dimensions the answer will be different. In one dimension, there could not be a point X as described above.
There might be some clever way of answering this problem. It reminds me a bit of Buffon's Needle.
|
|
Posted by Jer
on 2025-03-23 14:03:59 |
Initial thoughts
