1
$\begingroup$

I was given this problem recently in a job interview in which I did not succeed, however I found the problem itself very interesting, and have been trying to solve it since.

Question:

Given matchstick of length 1, and an infinite grid of similar matchsticks (i.e. an infinite grid of 1x1 squares), if you toss the matchstick randomly onto the grid, what is the probability that the matchstick lands overlapping at least one of the matchsticks in the grid?

My approach:

I decided to first define 3 variables:

  • $x =$ horizontal distance between lower end of landing matchstick and nearest grid matchstick to the left
  • $y =$ vertical distance between lower end of landing matchstick and nearest grid matchstick below
  • $\theta$ = landing angle of matchstick with grid horizontal

By definition:

  • $x, y$ ~ $U(0, 1)$
  • $\theta$ ~ $U(0, \pi)$
  • $x, y, \theta$ are all independent of each other

I then split the events of overlapping the horizontal and the vertical matchsticks in the grid, such that:

$$ P(Overlap) = P(OverlapsVertical) + P(OverlapsHorizontal) - P(OverlapsVertical \bigcup OverlapsHorizontal) $$

  • $P(OverlapsVertical) = P(y + sin(\theta) >= 1)$
  • $P(OverlapsHorizontal) = P(x + cos(\theta) >= 1)$

For overlapping vertical, because both y and theta are uniformly distributed, I could calcluate $P(OverlapsVertical)$ by:

  • Constructing the rectangle of possible values for $y$ and $\theta$
  • Integrating to find the proportion of area of this rectangle that satisfied the condition $y + sin(\theta) >= 1$

Doing the same for the horizontal case, I found that $P(OverlapsVertical) = P(OverlapsHorizontal) = 2/\pi$.

However, I realised that the events $OverlapsVertical$ and $OverlapsHorizontal$ are not independent, because they are both dependent on $\theta$, specifically $sin(\theta)$ and $cos(\theta)$ which are inversely related, and therefore:

  • $P(OverlapsVertical \bigcup OverlapsHorizontal) \not= P(OverlapsVertical) * P(OverlapsHorizontal)$

I then became stuck, and wondered if my approach to the entire problem was wrong. Is there a better way to solve this problem? Any input greatly appreciated. Thanks!

$\endgroup$
  • 2
    $\begingroup$ See Buffon's Needle Problem $\endgroup$ – Bram28 Jan 2 '18 at 22:07
  • $\begingroup$ @Bram28 thanks for the quick reply. I see how that applies to the individual events of crossing the vertical and crossing the horizontal (my problem is specifically Buffon's needle where t = l = 1, and hence agrees with my answer 2/π), however as far as I can tell it does not answer the question of crossing either the vertical or the horizontal, where these two events are not independent nor mutually exclusive. $\endgroup$ – Rory Devitt Jan 2 '18 at 22:20
  • $\begingroup$ Out of curiosity, which position were you applying for ? $\endgroup$ – Gabriel Romon Jan 2 '18 at 22:24
  • $\begingroup$ @GabrielRomon it was a quantitative trading position at a hedge fund $\endgroup$ – Rory Devitt Jan 2 '18 at 22:25
  • $\begingroup$ And the interviewer didn't give you a hint or a nudge in some direction ? $\endgroup$ – Gabriel Romon Jan 2 '18 at 22:31
1
$\begingroup$

The if the midpoint lands inside a box of dimensions: $(1-\cos\theta)\times(1-\sin\theta),$ then then the match will fit inside that square.

Due to the symmetry of the grid we only need to analyze $\theta \in [0, \frac {\pi}{4}]$

$\frac 1{\frac {\pi}{4}}\int_0^\frac {\pi}{4} (1-\cos\theta)\cdot(1-\sin\theta)\ d\theta$

$\endgroup$
  • $\begingroup$ The same argument works with Buffon's problem. $\endgroup$ – Gribouillis Jan 2 '18 at 23:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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