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 going to start by assuming that, if there is a solution, it's as valid for a large, but finite, number of farmers as it is for an infinite one.
The cases of one or two farmers are uninteresting, so let's start with 3 farmers. Two of these will form a pair, with the third attached to one of them. That is, in 2/3 of cases, there was a single transmission, and in the other case there were 2.
Applying the same line of reasoning to a large number of farmers, 2/3 of the cases will contain mutual nearest neighbors. Of the remaining 1/3, 2/3 will again have a nearest neighbor in an existing group; and so on.
In general, for some large number of farmers, F, there will be (2F/3^n) farmers in the nth group. Thus for, say, 200 farmers, there should be around 133 pairs, 44 groups of 3, 15 groups of 4, 5 groups of 5, and around 2 groups of 6 or more. Naturally, these groups overlap.
The answer to the first question is then 2/3.
The answer to the second involves expectation, which makes it difficult. In the example I gave, there would be around 133+(44*2)+(15*3)+(5*4)+(2*5)=296 transmissions for 200 people, around 1.5 transmissions per person.
In general, sum 1 to infinity 2n/3^n=3/2, so the actual number of farmers can be arbitrarily large.
I append a description of an algorithm for finding the routes.
* * * * * * *
Label all the distances between all the farmers from (1,2) to ((n-1),n) with some large n. That gives a total of 1/2n(n-1) possible distances, all different. Now sort all the labelled distances from the shortest to the longest. This is list(1).
In general, we seek the first occurrence of each number from 1 to n in either place in the labels in list(1). That number is then 'found', and the corresponding labelled distance is added to List(2). We need search for no further instances of that number.
List(2) is then added to until all the numbers from 1 to n are accounted for. (Note that there can never be more than (n-1) labelled distances in this list, and probably not that many, and never less than n/2).
Copy List(2), switch the order of the two numbers in the label and append to list(2). Sort ascending the lengthened list(2) first by distance, then by the first number in the label.
Starting with 1, the first item in List(2) will be the shortest distance (1,a). This starts a group. Check the first entry for a in the list. If it is (a,1) then the group is complete. If it is (a,b) then continue to b and repeat the process until the current entry in the list matches its inverse.
Continue with 2,3,... until n is reached. This will complete all the groups compliant with the problem, listed with their corresponding paths.
Edited on March 24, 2025, 10:41 pm
|
|
Posted by broll
on 2025-03-24 07:34:51 |
some thoughts
