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
Solution to 3 ii
j B k k N
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
adamodoherty
87 posts
#1 • 2 Y
This topic is linked to Problem 3.
Y by Adventure10, Mango247
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.
This post has been edited 6 times. Last edited by adamodoherty, Nov 15, 2017, 8:44 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
#2 • 4 Y
Y by v4913, HamstPan38825, Adventure10, Mango247
This is a surprise to me, because I recall when I looked at the numerical data for problem 3 it seemed to give $\frac{\pi}{105}$ very closely for both questions. I'll have to re-run that program to refresh my memory, so let me get back to you on that (as well as after I've looked more closely at what you've written).
This post has been edited 1 time. Last edited by v_Enhance, Nov 15, 2017, 12:44 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
adamodoherty
87 posts
#3 • 1 Y
Y by Adventure10
Redacted. Will hopefully be replaced soon.
This post has been edited 5 times. Last edited by adamodoherty, Nov 21, 2017, 12:12 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
adamodoherty
87 posts
#4 • 2 Y
Y by Adventure10, Mango247
Did you get a chance to rerun that program yet?
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
#5 • 3 Y
Y by v4913, HamstPan38825, Adventure10
Sorry for delay (thanksgiving). Program (in Python 3):
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
 
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))


Output:
0.02995633205687399
0.029689132739146293
The first number is the $\frac{\pi}{105}$ that we got from the random sample. The second is very close, but actually now that I'm re-running it it is always consistently a bit smaller, about $0.2968$--- so maybe they are not equal after all.

But $\frac{\pi}{105} \approx 0.261$ is definitely too small.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
hickory
792 posts
#6 • 1 Y
Y by Adventure10
We embed our line into the interval $[0,1]$. Let the first point be $x$ and the second point be y. Because of symmetry ($x<\frac{1}{2}\rightarrow y\geq x, x>\frac{1}{2}\rightarrow y\leq x$, we just rotate one 180 degrees to get the other) we can WLOG let $y\geq x$. Then our lengths are $x$, $y-x$, and $1-y$. We have the triangle inequalities $x \leq y-x+1-y$, $y-x\leq x+1-y$, and $1-y\leq x+y-x$, i.e. $x,1-y,y-x\leq \frac{1}{2}$. This means that when we take our double integral, $x$ ranges from $0$ to $\frac{1}{2}$ and $y$ ranges from $\frac{1}{2}$ to $\frac{1}{2}+x$. Then similarly to adamodoherty above, our integrand is $\sqrt{\frac{1}{2}\left(\frac{1}{2}-x\right)\left(\frac{1}{2}+x-y\right)\left(y-\frac{1}{2}\right)}$. We turn the last two terms in the radicand into a difference of squares and u-substitute $y'=y-\frac{x+1}{2}$ to "see" the semicircle better. Now our integral becomes: $\int^{\frac{1}{2}}_0 \int^{\frac{x}{2}}_{-\frac{x}{2}} \sqrt{\frac{1}{2}\left(\frac{1}{2}-x\right)\left[\left(\frac{x}{2}\right)^2-y'^2\right]} dy'dx$. The $dy'$ integral is just equal to $\frac{1}{2}\pi\left(\frac{x}{2}\right)^2$ because it's a semicircle's area, so our integral becomes $\int^{\frac{1}{2}}_0 \frac{1}{2}\pi\left(\frac{x}{2}\right)^2\sqrt{\frac{1}{2}\left(\frac{1}{2}-x\right)} dx$. A substitution $v=\frac{1}{2}-x$ with $dx=-dv$ gives $\frac{\pi}{8\sqrt2}\int^{\frac{1}{2}}_0\left(\frac{1}{2}-v\right)^2\sqrt{v} dv$ which is easily done by expanding and using the power rule to get $\frac{\pi}{8\sqrt2}\left(\frac{1}{6}\left(\frac{1}{2}\right)^{\frac{3}{2}}+\frac{2}{7}\left(\frac{1}{2}\right)^{\frac{7}{2}}-\frac{2}{5}\left(\frac{1}{2}\right)^{\frac{5}{2}}\right)$. Simplifying, we get $\frac{\pi}{840}$. Now we need to divide by the area over which we are taking the integral. This area is seen to be a right triangle with both legs $\frac{1}{2}$ by examining our inequalities above, so the area is $\frac{1}{8}$. Dividing gives our final expected area of $\frac{\pi}{105}=0.0299$
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!