6
$\begingroup$

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

$\endgroup$

closed as off-topic by f'', Gamow, Engineer Toast, Ric, mmking Nov 4 '15 at 15:20

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is off-topic as it appears to be a mathematics problem, as opposed to a mathematical puzzle. For more info, see "Are math-textbook-style problems on topic?" on meta." – f'', Gamow, Engineer Toast, Ric, mmking
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ You want the number with the biggest probability? I assume then there must be a trick. $\endgroup$ – Sleafar Nov 2 '15 at 17:58
  • 3
    $\begingroup$ 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. $\endgroup$ – Fimpellizieri Nov 3 '15 at 4:06
  • $\begingroup$ @Fimpellizieri Yes, uniformly distributed. $\endgroup$ – ghosts_in_the_code Nov 3 '15 at 9:42
  • 2
    $\begingroup$ Do you know the answer? $\endgroup$ – Lopsy Nov 4 '15 at 3:23
  • $\begingroup$ @Lopsy No, I don't. $\endgroup$ – ghosts_in_the_code Nov 4 '15 at 10:36
4
$\begingroup$

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

enter image description here

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.

$\endgroup$
  • 2
    $\begingroup$ +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. $\endgroup$ – Engineer Toast Nov 3 '15 at 15:28
  • $\begingroup$ @EngineerToast oh yeah you are right. $\endgroup$ – nivag Nov 4 '15 at 9:26
3
$\begingroup$

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.

enter image description here

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

enter image description here

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.

$\endgroup$
0
$\begingroup$

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


$\endgroup$
  • 10
    $\begingroup$ 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. $\endgroup$ – Milo Brandt Nov 3 '15 at 4:38

Not the answer you're looking for? Browse other questions tagged or ask your own question.