# Intersecting bug trail [closed]

A man picks up a huge circular dart board and shoots paintballs at it. $n$ paintballs manage to hit it. They are random and point-sized, for the purpose of this question. A bug is somewhere on the edge of the board.

It likes to eat paint, so it goes to the nearest smear of paint and eats it. It then goes to the nearest smear from there and eats that also. It repeats this process until they entire board is clean. Incidentally, the bug also leaves a trail behind, wherever it goes.

Question: How many times is this trail most likely to intersect itself? (Report as a function of $n$)

• You want the number with the biggest probability? I assume then there must be a trick. – Sleafar Nov 2 '15 at 17:58
• This looks like a math question to be honest. Also, I suppose by random you mean uniformly distributed? In the sense that the probability of a smear being in a region $R$ is given by the area of $R$ over the area of the circular dart board. – Fimpellizieri Nov 3 '15 at 4:06
• @Fimpellizieri Yes, uniformly distributed. – ghosts_in_the_code Nov 3 '15 at 9:42
• Do you know the answer? – Lopsy Nov 4 '15 at 3:23
• @Lopsy No, I don't. – ghosts_in_the_code Nov 4 '15 at 10:36

I also did a Monte Carlo simulation (N=10,000) and got a linear increase in the number of intercepts with $n$.

For $n\leq2$ there are no intercepts (excluding cases where two points are identical) by simple geometry.

For $3<n\leq20$ I get the following plot of average intercepts against $n$, which is approximately linear given the low number of repeats. (I didn't do n=3 because I initially thought it couldn't have any intercepts, but it can.) With an equation of approximately $$I=0.075n-0.3$$

Interestingly the number of intercepts for a given $n$ seems to be approximately binomial, which leads me to believe there may be an analytical solution to this although its beyond my knowledge.

• +1 but I dispute the case for $n=3$. The problem states that the bug is somewhere on the edge and not that it is on the edge near the point that is nearest to any edge. See this image that shows the trail in red. The bug starts on the edge in the bottom left and travels to each of the closest black paint balls. Its trail crosses once. – Engineer Toast Nov 3 '15 at 15:28
• @EngineerToast oh yeah you are right. – nivag Nov 4 '15 at 9:26

I also did a Monte Carlo simulation but extended the range a little. For 14 or less paint spots the "most likely" number of intersections is 0. For 15 paint spots this changes to 1.

For larger numbers of paint spots the "most likely" number of intersections rises linearly with number of paint spots. A reasonable approximate fit is

 Intersections ~= Floor(spots/12)


The following plot shows this out to 400 spots. For higher numbers of spots the number of intersections approximates a Gaussian distribution where the mean grows linearly with Spots and standard deviation grows as Sqrt(Spots)

See the following plot for 125, 150, 175, and 200 spots Although a simple probabilistic argument can probably explain the influence of number of spots on number of intersections I don't think there will be a practical analytical solution for the exact slope of intersections/spots relationship as it will be influenced by the shape of the target.

A quick monte carlo simulation ($N=100,000$) for $n\leq20$ is revealing.

In each of the lines at the bottom of this post, the first number is $n$, the second is the number of intercepts, and the third is the count of simulations that had the number of intercepts.

As you can see, even for $n$ as large as 20, and $N$ as large as 100,000, there was simply no intercept seen. (I was able to choose points in my code and see intercepts, so it wasn't an obvious coding error).

I suspect that the answer is 0 for all $n$. Making an intercept is simply very difficult, even for quite large $n$. I suppose eventually an increase in intercepts might happen, but I'm not sure.

3 0 100000

4 0 100000

5 0 100000

6 0 100000

7 0 100000

8 0 100000

9 0 100000

10 0 100000

11 0 100000

12 0 100000

13 0 100000

14 0 100000

15 0 100000

16 0 100000

17 0 100000

18 0 100000

19 0 100000

20 0 100000

Edit: Even with a few larger $n$'s, there are no interceptions:

100 0 1000

200 0 1000

300 0 1000

400 0 1000

500 0 1000

600 0 1000

• There are definitely self-intersecting paths for $n=4$, like this. Unless I've made a mistake or am misinterpreting this, I would be shocked if not one of 100,000 trials had such a situation, as the constraints are reasonably loose to cause such a thing. – Milo Brandt Nov 3 '15 at 4:38