Probability of the Center of a Square Being Contained in A Triangle With Vertices on its Boundary

Background : I happen to love solving tough problems. Problem is, I simply cannot answer some! It happened again today, as I attempted to solve the questions in this site: http://www.skytopia.com/project/imath/imath.html

This site seems to have really, really difficult questions, and in fact, I'm struggling to answer the second question! That struggle is not without reason, as you shall understand after reading the below question...

The Question is: 3 points are chosen at random along the square's outline. They then combine to form a triangle. What is the probability that the centre of the square will be 'engulfed' by this triangle?

My effort: I divided the square as below (I tried my best people,- assume the gaps between the line segments are points; I've been only ably to name the vertices of the square), -

                                 a1 a2 a3 a4
                               A __ __ __ __ B
                            d1  |           |  b1
                            d2  |           |  b2
                            d3  |           |  b3
                            d4  |__ __ __ __|  b4
                               D             C
                                 c1 c2 c3 c4

After having made these divisions and naming them accordingly...

• Considering point to be random, evaluated the probability of a point lying on any one of the sixteen segments to be 1/16.

• Realised centre of the square is engulfed in some cases of 3 points lying on (some examples):-

  _(a1,b3,c3);(a2,b4,c4);(a3,c1,d1);(a4,c2,d2)_
  _(b1,c3,d3);(b2,c4,d4);(b3,d1,a1);(b4,d2,a2)_
  _(c1,d3,a3);(c2,d4,a4);(c3,a1,b1);(c4,a2,b2)_
  _(d1,a3,b3);(d2,a4,b4);(d3,b1,c1);(d4,b2,c2)_
  

• Realised that I'm not accounting for so many more favourable cases (Not able to aptly apply concept of permutation and combination in this question).

• Realised that I'm not able to calculate the sample space.

• Realised that the answer is much tougher to compute because I'm not accounting for special cases of collinearity, as well as cases where the vertices and points of separation in my diagram (Not able to assign those points any segment; even if one for each, square's vertices cause problems when evaluating cases, preventing successful generalisation)

A convincing, ingenious, enlightening and accurate solution to question bolded above will be immensely appreciated.

Solution 1:

The answer is $\frac{1}{4}$. Given any two points $P$ and $Q$ on the square of side $s$ (regardless of whether they are on the same, different, or adjacent sides), consider the shortest path (of length $d$) along the square between $P$ and $Q$. (This is green in the picture below.) For a random pair of points, $d$ is on average length $s$. For a third point $R$ on the square, $\Delta PQR$ will enclose the center if and only if $R$ is on the reflection (purple) of the path of length $d$ through the center. The purple path has average length $s$, so the probability that $\Delta PQR$ encloses the center is $\frac{s}{4s}=\frac{1}{4}$.

Solution 2:

The answer is $\frac14$ and there is no need to do any complicated integral!

For this particular problem, it will be easier to attack if we generalize a little bit.

Let $D$ be any centrally symmetric convex domain in $\mathbb{R}^2$, centered at origin $O$ and its boundary $\partial D$ is a rectifiable curve with finite length $\ell$. Consider the problem of randomly and uniformly (according to arc-length) picking $3$ points from $\partial D$, forming a triangle from them and then determine the probability for such a triangle to contain the origin.

Let $\gamma : [0,\ell] \to \partial D$ be a parametrization of $\partial D$ by arc-length, oriented counter-clockwisely with respect to $D$. Let us extend it to a periodic function $\gamma : \mathbb{R} \to \partial D$ with period $\ell$.

For any $x \in \mathbb{R}$, consider $\overline{\gamma(x) O}$, the line joining $\gamma(x)$ with the origin $O$. Since $D$ is convex and $O$ is in its interior, $\overline{\gamma(x)O}$ intersect $\partial D$ at two and two points. Let $\gamma(y)$ be the other point the line intersect with $\partial D$. Since $D$ is centrally symmetric, the two arcs joining $\gamma(x)$ and $\gamma(y)$ has equal length. This implies $x - y$ is an odd multiple of $\frac12\ell$. This has an interesting consequence...

Pick any $3$ points $p,q,r$ from $\partial D$ randomly. Label them such that they orient around the $\partial D$ in counter-clockwise manner. We can always find $3$ real numbers $x,y,z$ from $\mathbb{R}$ such that

$$(p, q, r ) = (\gamma(x),\gamma(y),\gamma(z))\quad\text{ and }\quad x \le y \le z \le x + \ell$$

The consequence is in order for $\triangle pqr$ to contain $O$, we need $$ 0 \le y - x \le \frac12\ell,\quad 0 \le z - y \le \frac12\ell \quad\text{ and }\quad 0 \le (x+\ell) - z \le \frac12\ell $$

To see why this is the case, notice $$O \text{ inside } \triangle pqr\quad\iff\quad \begin{array}{rcl} ( O,r & \text{ lies on same side of } & \overline{pq} )\\ \verb/and / ( O,p &\cdot\cdot& \overline{qr} )\\ \verb/and / ( O,q &\cdot\cdot & \overline{rp})\\ \end{array} $$ Consider the families of lines $\overline{p_t q_t}, t \in (0,1]$ joining $$p_t \stackrel{def}{=}\gamma\left(\frac{x+y}{2}+t\frac{x-y}{2}\right) \quad\text{ and }\quad q_t \stackrel{def}{=}\gamma\left(\frac{x+y}{2}-t\frac{x-y}{2}\right).$$ When $t$ is small, $O, r$ lies on same side of $\overline{p_tq_t}$. When we increase $t$ from $\approx 0$ to $1$, $O$ crosses the line $\overline{p_tq_t}$ at those places where

$$t (y-x) = \left| \left(\frac{x+y}{2}+t\frac{x-y}{2}\right) - \left(\frac{x+y}{2}-t\frac{x-y}{2}\right) \right| $$ is an odd multiple of $\frac12 \ell$.

• If $y - x < \frac12\ell$, this never happens.
• If $y - x > \frac12\ell$, it happens once.

This means $O,r$ lies on same/different side of $\overline{pq} = \overline{p_1q_1}$ when $y - x$ is smaller/greater than $\frac12\ell$ respectively. Same situation for the other two cases.

For any fixed $x$, let $\lambda = y - x, \mu = z - y, \nu = (x+\ell) - z$. The possible choices of $( \lambda, \mu, \nu )$ forms an equilateral triangle in $\mathbb{R}^3$:

$$0 \le \lambda, \mu, \nu \quad\text{ and }\quad \lambda + \mu + \nu = \ell$$

In order for $\triangle pqr$ to contain $O$, the constraint is $(\lambda, \mu, \nu)$ falls inside a smaller equilateral triangle:

$$0 \le \lambda, \mu, \nu \le \frac12\ell\quad\text{and}\quad \lambda + \mu + \nu = \ell$$

It is clear the smaller triangle is $\frac14$ in area of the first triangle. This means once we fix $p$, the conditional probability for $\triangle pqr$ to contain $O$ is $\frac14$.

Since this is true for all $x$, the probability for $\triangle pqr$ to contain $O$ is also $\frac14$.

Choosing the center of a square as origin, a square fits our requirement for $D$.
As a result, the probability we seek is $\frac14$.

Solution 3:

I get $\frac{1}{4}$.

The crux is to figure out the conditional probability in two cases: two points are on the same side, the third point on the opposite side, and three points are on different sides.

Suppose WOLG the third point $z$ is on side 1.

There are 3 (well, 4) possible cases

1. No possible triangle--occurs when either all three points are on the same side, or 2 points are on the same side and the third is on an adjacent side (technically there's a possible triangle here, but it's probability 0).
2. Two points on same side, third point on opposite side (blue above).
3. Three points on different sides (green above).

Conditional on case 1, the probability of a triangle encompassing the center is 0.

Conditional on case 2, the probability is $\frac{1}{3}$.

To see this, consider the following picture:

For (WLOG) $x>z$, there can only be a triangle for $y\in[x,z]$. Thus, conditional on the points being arranged as in case 2, the probability of an appropriate triangle is:

$\intop_0^1\intop_0^x \intop_z^x dy dz dx = \frac{1}{6}$

We then double this to cover $z>x$ to get $\frac{1}{3}$.

Conditional on case 3, @GerryMyerson has already gone through why the likelihood is $\frac{1}{2}$.

In total, there are 64 possibilities of side assignments for the three points, so each arrangement has probability $\frac{1}{64}$.

For each side that $z$ lands on, there are 7 side arrangements of $x,y$ that result in case 1;

3 arrangements resulting in case 2;

and 6 arrangements in case 3.

So in total, the probability of a triangle encompassing the center is: $\frac{4(6(\frac{1}{2})+3(\frac{1}{3}))}{64}=\frac{1}{4}$

Updated to reflect comments & correct algebra mistake pointed out by @achillehui.

Solution 4:

To extend achille hui's answer even further, we can prove the following statement:

Let $\mu$ be a probability measure on the plane which is centrally symmetric around some point $O$ (i.e. such that if $S'$ is the reflection of $S$ through $O$, then $\mu(S)=\mu(S')$) and such that the measure of any line through $O$ is $0$. Then, the probability of three points chosen according that measure containing $O$ is $\frac{1}4$.

This eliminates the "convex" requirement of achille hui's answer (and is even slightly more general than that). Intuitively this means:

If we choose three points according to the same distribution, such that $A$ and its reflection through $O$ are equally likely to show up, then the probability that $O$ will be in the triangle formed by those points is $\frac{1}4$.

And it of course applies here, as choosing random points on the boundary of a square satisfies the condition.

Consider that once we have chosen two points $a$ and $b$, we can easily calculate the probability of the third forming a triangle as the measure of a certain "wedge" of the space:

where the shaded wedge is where the third point must lie. We will say that $p$ is the measure of that wedge (and the one opposite it), which is the probability of choosing an appropriate $c$ given $a$ and $b$.

As symmetry will allow us to extend this argument to either case, assume $b$ is to the right of the line $aO$, as is shown in the diagram above. If we fix $a$, then we can calculate that the measure of the set of $b$ such that the shaded region has measure of at least $p$ - in particular, this means that $b$ lies in region IV as noted in the diagram, which happens with probability $2p$ (the $2$ appears since we assumed $b$ was in region II or IV) - so the CDF of $p$ upon choosing $b$ at random is $P(p<k)=2k$. This probability is unconditional as the symmetries of the problem and the fact that $a$ was chosen arbitrarily suffice to eliminate the fact that we fixed $a$ and the side of the line $aO$ that $b$ was on.

Knowing this, we can reduce the original problem to choosing some $a$, which doesn't matter, then picking $p$ out of a uniform distribution on $\left[0,\frac{1}2\right]$ (which represents choosing $b$), and finally picking a $c$ in the desired wedge with probability $p$. The overall probability of $c$ being in that wedge (and hence forming a triangle containing the origin) is thus expressed as $$\int_{0}^{\frac{1}2}2p\,dp=\frac{1}4.$$