Happy Thanksgiving! Please note that there are no classes November 25th-December 1st.

MIT PRIMES/Art of Problem Solving

CROWDMATH 2017: The Broken Stick Problem

a
p
Broken Stick J
Problem 3: Expected Area on "Biased Splits"
j B k k N
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
always_correct
809 posts
#1 • 1 Y
This topic is linked to Problem 3.
Y by Adventure10
Notice that if we do the opposite procedure, that is, place the next break in the unit length in the smaller segment, we end up with no possible triangle. This is because the larger segment must have length $> \frac{1}{2}$, and as this segment is not broken up any further, it remains larger than the semiperimeter. Thus, as given before, the area expected is $\frac{\pi}{105}$, as noted before. The same applies to the second scenario in which we place the next cut in the rightmost segment.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
goodbear
1108 posts
#2 • 3 Y
Y by Tawan, Adventure10, Mango247
The probability distributions are not the same in terms of creating triangles. You can see this by analyzing the probability of having the leftmost segment being $\le 1/4$ in both the original and current distributions. They turn out to be different probabilities.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
goodbear
1108 posts
#3 • 3 Y
Y by Tawan, Adventure10, Mango247
Oh wait, I think I see what you were trying to say now. To put your thinking in other words, even though these distributions are different, if they make a triangle, these distributions are the same. You were right to say that the answer is $\frac{\pi}{105}.$ Sorry for the confusion! :blush:
This post has been edited 1 time. Last edited by goodbear, Apr 1, 2017, 7:26 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
shinichiman
3212 posts
#4 • 3 Y
Y by Tawan, Adventure10, Mango247
Coming back from Dr. Tanya Khovanova's comment in the pdf:

Probability $P_A$ of choosing two points in $[0,1]$ randomly to form triangle and probability $P_B$ of choosing first point randomly and then choose second point in larger interval to form triangle is different I believe. Say, if the first point is $a<\tfrac 12$ then probability $P_B$ includes event where we choose the second point in smaller interval $[0,a]$ but probability $P_B$ doesn't. One can expected that $P_B=2\ln(2)-1>P_A=\tfrac 14$ from this.

For this reason, I think the expected area should be $\frac{\pi/840}{\ln(2)-\frac 12}$. I only change the denominator part comparing to expected value in Proposition 1(i).1. which is $\frac{\pi/840}{1/8}$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
shinichiman
3212 posts
#5 • 4 Y
Y by v_Enhance, Tawan, Adventure10, Mango247
It seems my answer is also incorrect. I wrote a code for this (following goodbear's code) and it gives answer of $0.0296902006304548$ in $5 \cdot 10^7$ samples.

import sys
import random
def sample():
    while True:
        x=random.random()
        if (x>0.5):
            y=random.uniform(0,x)
            s,a,b,c=0.5,y,x-y,1-x
            if max(a,b,c)<s:
                area=(s*(s-a)*(s-b)*(s-c))**0.5
                return area
        if (x<0.5):
            y=random.uniform(x,1)
            s,a,b,c=0.5,x,y-x,1-y
            if max(a,b,c)<s:
                area=(s*(s-a)*(s-b)*(s-c))**0.5
                return area
 
samples=int(input("How many samples would you like? "))
averageSample=sum([sample() for i in range(samples)])/samples
print(averageSample)
This post has been edited 2 times. Last edited by shinichiman, Apr 7, 2017, 1:34 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
j___d
340 posts
#6 • 4 Y
Y by shinichiman, Tawan, Adventure10, Mango247
Worth noting the code's output is $\frac \pi {105}$ to three decimal digits.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6837 posts
#7 • 5 Y
Y by shinichiman, v4913, HamstPan38825, Adventure10, Mango247
So I agree the answer empirically is $\pi/105$ for both answers, but I'm also not convinced the proof works. Let me interpret what's been said in this thread so far.

We'll let $x,y \in [0,1]$ represent the location of the first
and second break, respectively.
Let $\mathcal S$ denote the space of points $(x,y) \in [0,1]^2$.
Then:
  • Let $\mathcal T$ be the region consisting of points for which we obtain a triangle.
  • Let $\mathcal A$ be the region consisting of points for which $y$ lies in the larger segment after breaking at $x$.
  • Let $\mathcal B$ be the region consisting of points for which $y$ lies to the right of $x$.
Let $F = F(x,y)$ denote the area of the triangle. We know that \[ \frac{\int_{\mathcal T} F}{\int_{\mathcal T} 1} = \frac{\pi}{105}. \]The claim is that the answer is the same if
we replace $\mathcal T$ by either $\mathcal T \cap \mathcal A$ or $\mathcal T \cap \mathcal B$.

Indeed, we easily have $\mathcal T \subset \mathcal A$. To prove this note that if $(x,y) \notin \mathcal A$ then $x$ and $y$ are on the same side $\frac12$, so they don't form a triangle anyways. I don't actually see why $\mathcal T \subset \mathcal B$, though (you probably need a symmetry argument).

My concern is that I don't think the answer to (a) is just replacing $\mathcal T$ with $\mathcal T \cap \mathcal A$ or $\mathcal T \cap \mathcal B$, because the procedure will bias some points of $\mathcal B$ more. To be concrete, look at $\mathcal B$. When we do this procedure, the chance that $x \ge 0.9$ is $0.1$. But the area ratio $[\{x \ge 0.9\} \cap \mathcal B] / [\mathcal B]$ is far less than $0.1$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
talkon
276 posts
#8 • 3 Y
Y by Tawan, Adventure10, Mango247
Hmm, I think a symmetry argument works here.
Since we obtain a triangle for $(x,y)$ iff we obtain a triangle for $(y,x)$, and $F(x,y)=F(y,x)$, both $\mathcal T$ and the $F(x,y)$ is symmetric about the line $x=y$.
Hence $\int_{\mathcal T\cap\mathcal B} F = \int_{\mathcal T; x>y} F =\frac{1}{2}\int_{\mathcal T} F$
and $\int_{\mathcal T\cap\mathcal B} 1 = \int_{\mathcal T; x>y} 1 =\frac{1}{2}\int_{\mathcal T} 1$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6837 posts
#9 • 4 Y
Y by v4913, HamstPan38825, Adventure10, Mango247
Sure, so that's the symmetry argument. But again I'm not sure this solves the problem, because it's not obvious to me the answer it (a) is $\int_{T \cap \mathcal A} F \div \int_{T \cap \mathcal A} 1$, similarly for (b).
This post has been edited 1 time. Last edited by v_Enhance, Apr 20, 2017, 12:23 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6837 posts
#11 • 4 Y
Y by v4913, HamstPan38825, Adventure10, Mango247
Let me make my complaint more explicit by means of concrete example.

Let's consider part (a), but instead of $F(x,y) = \text{area triangle}$, we instead use $F(x,y) = (x-\frac12)^2$.
Here's the implementation:

import sys
import random
 
def sampleS():
    x = random.random()
    y = random.random()
    return (x,y)
 
def sampleA():
    x=random.random()
    if (x>=0.5):
        y=random.uniform(0,x)
    if (x<0.5):
        y=random.uniform(x,1)
    return (x,y)
 
def inT(x,y):
    if (x>=0.5):
        s,a,b,c=0.5,y,x-y,1-x
    if (x<0.5):
        s,a,b,c=0.5,x,y-x,1-y
    return max(a,b,c)<s
 
def f(x,y):
    if (x>=0.5):
        s,a,b,c=0.5,y,x-y,1-x
    if (x<0.5):
        s,a,b,c=0.5,x,y-x,1-y
    # return (s*(s-a)*(s-b)*(s-c))**0.5
    return (x-0.5)**2
 
def avg(data):
    return sum(data)/float(len(data))
 
# Experiment 1
data1 = [f(*p) for p in [sampleS() for _ in xrange(10**5)] if inT(*p)]
print avg(data1)
 
# Experiment 2
data2 = [f(*p) for p in [sampleA() for _ in xrange(10**5)] if inT(*p)]
print avg(data2)


Sure enough, the results are different: $0.041$ in first case and $0.034$ in second case.

But if I replace $F(x,y)$ with area triangle, or even $a^2+b^2+c^2$, then the results seem to match up. So there must be something about the function $F$ itself that is involved in part (a).
This post has been edited 1 time. Last edited by v_Enhance, May 26, 2017, 2:51 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6837 posts
#12 • 3 Y
Y by v4913, HamstPan38825, Adventure10
Quick bump on this!

I think the symmetry argument should work for (b), and I've split the write-up for this in the main document as a result. But I think we should figure out what is going on with (a). We should be almost there!
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
walnutwaldo20
508 posts
#13 • 3 Y
Y by Tawan, Adventure10, Mango247
If I am understanding correctly, we have shown that the answer for b is still $\frac{\pi}{105}$. Then, should it not be that a is also $\frac{\pi}{105}$? Half of the time the second point will be chosen to the left of the first and the other half of the time it will be chosen to the right. For b, if the left side is larger, then no triangles will work there. In other words, b really only includes triangles where the first point is chosen to the left of $\frac{1}{2}$. Symmetry tells us that if we always chose the second points to the left of the first, then the expected area is also $\frac{\pi}{105}$. Therefore, the expected are for a is simply $\frac{1}{2}\cdot\frac{\pi}{105}+\frac{1}{2}\cdot\frac{\pi}{105}=\frac{\pi}{105}$. I feel like I am missing something important.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6837 posts
#14 • 3 Y
Y by v4913, HamstPan38825, Adventure10
I mentioned this in another thread but saying it again here: I'm looking more closely at the output from the program from earlier, and I'd like to retract the claim I made that (a) is $\pi/105$. It seems that actually, the answer is a hair smaller, though I'm not sure what the closed form is.

import sys
import random
 
def sampleS():
    x = random.random()
    y = random.random()
    return (x,y)
 
def sampleA():
    x=random.random()
    y=random.uniform(0,x) if (x>=0.5) else random.uniform(x,1)
    return (x,y)
 
def inT(x,y):
    a = min(x,y)
    b = abs(x-y)
    c = 1-max(x,y)
    s = 0.5
    return max(a,b,c)<s
 
def f(x,y):
    a = min(x,y)
    b = abs(x-y)
    c = 1-max(x,y)
    s = 0.5
    return (s*(s-a)*(s-b)*(s-c))**0.5
    # return a**2+b**2+c**2
 
def avg(data):
    return sum(data)/float(len(data))
 
# Experiment 1
data1 = [f(*p) for p in [sampleS() for _ in range(10**6)] if inT(*p)]
print(avg(data1))
 
# Experiment 2
data2 = [f(*p) for p in [sampleA() for _ in range(10**6)] if inT(*p)]
print(avg(data2))


The output on my first run was
0.029887953893296657
0.029670400655489457

and the second value is consistently a little bit smaller than the first value of $\pi/105$ (over several runs).
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Nirmay
76 posts
#15 • 2 Y
Y by Adventure10, Mango247
Do you know by how much it varies every time? It might be some fraction of Pi. If every time you run it you get a different answer you might want to average the results and see what you get. That could give us a clue.
This post has been edited 1 time. Last edited by Nirmay, Dec 2, 2018, 1:44 AM
Reason: I edited this because I realized the difference could vary every time you run the program.
Z K Y
N Quick Reply
G
H
=
Page Feed | J
Linked Item Topics
G
Topic
First Poster
Last Poster
H
Problem 3: Expected Area on "Biased Splits"
always_correct   13
N Dec 2, 2018 by Nirmay
Notice that if we do the opposite procedure, that is, place the next break in the unit length in the smaller segment, we end up with no possible triangle. This is because the larger segment must have length $> \frac{1}{2}$, and as this segment is not broken up any further, it remains larger than the semiperimeter. Thus, as given before, the area expected is $\frac{\pi}{105}$, as noted before. The same applies to the second scenario in which we place the next cut in the rightmost segment.
13 replies
always_correct
Mar 9, 2017
Nirmay
Dec 2, 2018
J
H
Solution to 3 ii
adamodoherty   5
N Sep 26, 2018 by hickory
Here I think is a solution to the question: what is the expected area when we pick the second point from inside the largest interval?

Call the small first interval $y$, call $x$ the leftmost piece from the second break. It's more useful to not define the the larger interval.

We can then say that the area of the triangle is obviously $\sqrt{\frac12\left(\frac12 - y\right)\left(\frac12-x\right)\left(\frac12-(1-y-x)\right)}$ and so the average area is $\frac1{\frac12-(\frac12-y)}\int_{\frac12-y}^{\frac12}\sqrt{\frac12\left(\frac12 - y\right)\left(\frac12-x\right)\left(\frac12-(1-y-x)\right)}\ dx$

From here we can make multiple simplifications:

$$
   \frac1y \sqrt{\tfrac12(\tfrac12-y)} \int_{\frac12-y}^{\frac12} \sqrt{\left(\frac12-x\right)\left(\frac12-(1-y-x)\right)}\ dx
$$
We now look for a substitution to solve which was initially where I got stuck but $u=x+y-\frac12$ works and makes the integral

$$\frac1y \sqrt{\tfrac12(\tfrac12-y)} \int_0^y \sqrt{u(y-u)} dx$$
It's pretty obvious when considering the substitution now that $\sqrt{u(y-u)}$ is a semicircle centered at ($\tfrac y2$, $0$). The semicircle has area $\frac12 \pi (\frac y2)^2$ and so our equation changes to $\frac\pi 8 y\sqrt{\frac12(\frac12-y)}$

The integral which is then formed, $2\int_0^{1/2}\frac\pi 8 y \sqrt{\tfrac12(\tfrac12-y)}\ dy$, would be pretty easy to solve by hand but I just plugged it into symbolab (https://www.symbolab.com/solver/definite-integral-calculator/2%5Cint_%7B0%7D%5E%7B%5Cfrac%7B1%7D%7B2%7D%7D%20%5Cfrac%7B%5Cpi%7D%7B8%7Dy%5Csqrt%7B%5Cfrac%7B1%7D%7B2%7D%5Cleft(%5Cfrac%7B1%7D%7B2%7D-y%5Cright)%7Ddy) which yields

$$2\int_0^{1/2}\frac\pi 8 y \sqrt{\tfrac12(\tfrac12-y)}\ dy = {\pi\over120}$$
Which is unsurprisingly pretty close to the other value we found of ${\pi\over105}$.

I am currently working on the other distribution discussed in problem three, hope this doesn't take too long.

Anyway, this seems right to me. Let me know if you see any errors.
5 replies
adamodoherty
Nov 14, 2017
hickory
Sep 26, 2018
J
H
Answer to Problem 3
walnutwaldo20   10
N Apr 6, 2017 by shinichiman
(a)
Recall that the lengths of the three sides of a triangle are all shorter than the semiperimeter. If we take a segment of length one and break in into two smaller segments, one will be shorter than $\frac{1}{2}$ (the semiperimeter). Since the second point will be chosen from the larger interval, we are gaurenteed at least one segment being shorter than the semiperimeter. Now we just need to find that chance that the second point will break the smaller interval into lengths shorter than the semiperimeter.

Define $P(l)$ as the probability that the second point will split the an interval of length $l$ into two lengths shorter than the semiperimeter, for $\frac{1}{2} <  l < 1$. A quick analysis shows that the second point must be more than $l-\frac{1}{2}$ from the ends of the interval. This means $P(l) = \frac{1}{l}-1$.
Integrating this function between $\frac{1}{2}$ and $1$ gives $ln(2)-\frac{1}{2}$. The range of the function was $\frac{1}{2}$, so dividing gives the final probability of $\boxed{2ln(2)-1}$

(b)
When choosing from right interval, there is a $\frac{1}{2}$ chance that we are choosing from the larger interval and a $\frac{1}{2}$ chance we are choosing from the smaller interval. This said, we already know the probability of creating a triangle if the second point is chosen from the larger interval. We also know the probability of creating a triangle when choosing from the smaller interval. The larger interval must have a length greater than $\frac{1}{2}$, so if we do not split it, the probability of creating a triangle is $0$.
So the probability for part b is $\frac{1}{2}\cdot(2ln(2)-1) = \boxed{ln(2)-\frac{1}{2}}$

If there is any error in this, or if something could be worded better, feel free to comment.
10 replies
walnutwaldo20
Feb 9, 2017
shinichiman
Apr 6, 2017
J
No more topics!
H
J
H
Problem 3: Expected Area on "Biased Splits"
always_correct   13
N Dec 2, 2018 by Nirmay
Notice that if we do the opposite procedure, that is, place the next break in the unit length in the smaller segment, we end up with no possible triangle. This is because the larger segment must have length $> \frac{1}{2}$, and as this segment is not broken up any further, it remains larger than the semiperimeter. Thus, as given before, the area expected is $\frac{\pi}{105}$, as noted before. The same applies to the second scenario in which we place the next cut in the rightmost segment.
13 replies
always_correct
Mar 9, 2017
Nirmay
Dec 2, 2018
J