9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I would say symmetry is key: after modding out the symmetries, the number of remaining triangles is not that large. $\endgroup$ – Hrodelbert Feb 27 '15 at 9:19
  • $\begingroup$ Note that the constraint in this problem - that the points form a triangle. This means they cannot all be on the same side. This suggests you will have to consider two different cases, where the points are on three different sides and where the points are on two different sides. $\endgroup$ – Peter Webb Mar 1 '15 at 10:55
  • $\begingroup$ ^I've noted this, but I'm seriously not able to move ahead. Also, there are many cases: all on same side,on two sides, on three sides, one on vertex and 2 on same side, one on one vertex and two on different sides, two on different vertices and one on one particular side (Many cases here as well)... So this approach is too cumbersome. $\endgroup$ – Kugelblitz Mar 1 '15 at 11:00
  • $\begingroup$ Diving the square's sides by 4 is just to have a starting point right? As I understand the problem each vertex of the triangle can be on a continuous set of points. $\endgroup$ – Gonate Mar 1 '15 at 11:01
  • $\begingroup$ ^Yes correct. That was just my approach. In reality, this doesn't even get me 0.01% closer to the solution. $\endgroup$ – Kugelblitz Mar 1 '15 at 11:02
6
+100
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Goodness, now that's a good answer. Could you explain the inequalities which are the conditions for p,q,r to contain the origin? I couldn't follow that part very well... And @meelo I might... give the bounty to Steve Kass if he explains one simple statement. You can then give the bounty to achille hui (Who I think also deserves a bounty..in fact I thought I'll give two, but since you're willing to give, I'll give you the chance) Achille I'm still going to upvote and in fact accept this answer by 2-3 days or so, because it's really good. $\endgroup$ – Kugelblitz Mar 2 '15 at 1:05
  • $\begingroup$ @achillehui Could you please check my other bounty question? Seeing as you're really good at integration, you might be able to help. $\endgroup$ – Kugelblitz Mar 2 '15 at 1:26
  • $\begingroup$ @Kugelblitz I updated the answer to elaborate the condition, I hope this make things a little bit clearer. $\endgroup$ – achille hui Mar 2 '15 at 3:56
  • $\begingroup$ @Kugelblitz For the integral in other bounty question, I cannot find any pattern in the integrand and it is way beyond me. $\endgroup$ – achille hui Mar 2 '15 at 4:01
  • $\begingroup$ Alright. And sorry to trouble, could you take a look at this and try solving it? @achillehui math.stackexchange.com/questions/1168651/… $\endgroup$ – Kugelblitz Mar 2 '15 at 4:32
16
+50
$\begingroup$

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}$.

enter image description here

$\endgroup$
  • $\begingroup$ Nice, intuitive, proof. (+1) $\endgroup$ – AvZ Mar 1 '15 at 20:15
  • $\begingroup$ I really like this proof $\endgroup$ – MichaelChirico Mar 1 '15 at 23:06
  • 4
    $\begingroup$ Meelo’s answer addresses it more rigorously, but try this: Imagine the square is made of wire. Choose $P$ at random, then before choosing $Q$, cut the square at $P$ and unfold it into a line segment of length $4s$. Point $Q$ will be equally likely to be anywhere on the segment, and $d$ is the distance between $Q$ and its nearest endpoint. As the possible position of $Q$ moves at a constant rate from one end to the other, $d$ increases steadily from $0$ to $2s$, then back to $0$, with an average of $1$. (I’m trying to avoid defining random and average technically, so I hope this is helpful.) $\endgroup$ – Steve Kass Mar 2 '15 at 1:11
  • 1
    $\begingroup$ ^ For that pun sir, you get my bounty. $\endgroup$ – Kugelblitz Mar 2 '15 at 1:24
  • 1
    $\begingroup$ I'll give you the bounty in the last day; that way, more people come across this question, and the succinct and excellent answers also have a chance to be appreciated. $\endgroup$ – Kugelblitz Mar 2 '15 at 7:04
5
$\begingroup$

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.

Possibilities when $z$ 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:

enter image description here

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.

$\endgroup$
  • $\begingroup$ Thank you for your wonderful answer! $\endgroup$ – Kugelblitz Mar 2 '15 at 1:09
4
$\begingroup$

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:

enter image description here

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

$\endgroup$
  • $\begingroup$ It is my desire that that image be centered, but I do not know how to accomplish that. If some kind editor would do so, it would make me happy. $\endgroup$ – Milo Brandt Mar 1 '15 at 20:29
  • $\begingroup$ Your image has $c$ where I think you wanted "o". $\endgroup$ – DanielV Mar 1 '15 at 20:44
  • $\begingroup$ Hmm, this argument can fail if the measure is singular enough. Consider the limiting case when you can only choose the points from the $4$ corners of a square, you get $\frac{9}{16}$ instead of $\frac14$. Looks like if the admissible values of $p$ does not cover the whole range of $[0,\frac12]$, $\text{CDF}(k) = P( k > p )$ need not equal to $2k$ in general... $\endgroup$ – achille hui Mar 2 '15 at 5:23
  • $\begingroup$ @achillehui Good point. I added a condition which should address that. I'll have to think if there's something more precise that "the triangle $abc$ contains $O$" that can address that (i.e. if we can solve the issue by defining whether said triangle is open or closed or some combination thereof) $\endgroup$ – Milo Brandt Mar 2 '15 at 5:30
  • $\begingroup$ @Meelo: Thanks for offering the bounty and enhance the visibility this way. It's a pleasure to see all these different approaches! :-) (+1) $\endgroup$ – Markus Scheuer Mar 5 '15 at 10:58
0
$\begingroup$

The "points on three sides" case is pretty easy. Assume, without loss of generality, that the three sides are the left, top, and right. If the line segment joining the points on the left and right sides passes below the center, the center will be in the triangle; if that line segment passes above the center, the center won't be in the triangle. It doesn't matter where on the top the third point is.

By symmetry, the line segment joining the points on the left and right sides is just as likely to pass above the center as below. So (in the "points on three sides" case) the probability the center is inside the triangle is one-half.

$\endgroup$
  • $\begingroup$ Alright, thanks for the input sir. Please do update your answer with more and more details as time progresses; we're far away from the solution as of now, and must try our best if we're to get the solution. Thanks once again. $\endgroup$ – Kugelblitz Mar 1 '15 at 12:00
  • $\begingroup$ What more details? I think all the details are there, for the points-on-three-sides case. The points-on-two-sides case, wasn't that settled in the comments? $\endgroup$ – Gerry Myerson Mar 1 '15 at 12:01
  • $\begingroup$ ^I find the actual calculation of that quite hard (I'm still in the process), and your solution addresses one case. Thank you for that input; could you please try and sum up all cases? I can't give you the bounty unless the solution calculates the probability, in a solution which is clear and that encompasses all cases involved. $\endgroup$ – Kugelblitz Mar 1 '15 at 12:06
  • $\begingroup$ I don't much care about the bounty. I'm happy to leave it to you to sum up all the cases. $\endgroup$ – Gerry Myerson Mar 1 '15 at 12:08

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.