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(ii) Possible Solution Path
j B k k N
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mathcrazymj
690 posts
#1 • 2 Y
This topic is linked to Problem 1.
Y by Adventure10, Mango247
Look at my solution to problem 5 in this pdf: http://submissions.usamts.org/Year28/Round1/34279-1476743929-USAMTS%202016%20Matthew%20Roth.pdf

I found some useful results about cyclic quadrilaterals that may generalize to Problem(ii)

EDIT: I'll think about it some more but I think this problem can be solved by breaking n-gons into a bunch of quadrilaterals and maybe 1 triangle (depending on n) and maximizing the areas by making all the quadrilaterals cyclic and the triangle equilateral
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 mathcrazymj, v4913, HamstPan38825, Adventure10
To summarize the result: http://www.maa.org/programs/faculty-and-departments/classroom-capsules-and-notes/maximizing-the-area-of-a-quadrilateral shows the following theorem.
Quote:
Theorem: Given four side lengths $a$, $b$, $c$, $d$ of a quadrilateral, the maximal possible area is achieved when $ABCD$ is cyclic.

That gives us a lot to work with in the $n=4$ case. :) That's something we could work on first, or we could try to think about how to solve this for general $n$.
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
#3 • 4 Y
Y by v4913, HamstPan38825, Adventure10, Mango247
I want to quickly bump this because I think that it really should be quite possible to compute the expected area of the maximal quadrilateral, now that we know it's cyclic.

To be precise, we solved (iirc) the earlier problem by integrating $\sqrt{s(s-a)(s-b)(s-c)}$ over the permissible region. In order to knock the $n=4$ case out it would basically be sufficient to do the same thing except with $\sqrt{(s-a)(s-b)(s-c)(s-d)}$, which is the formula for a cyclic quadrilateral's area. I haven't thought about the details but I think this wolud be a good thing to try.

As usual, we could also get numerical estimates via code.
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
#4 • 1 Y
Y by Adventure10
v_Enhance wrote:
As usual, we could also get numerical estimates via code.

  1. # This program will sample a cyclic quadrilateral's area (with the broken stick distribution).
  2. # It will ask you to enter how many times you want to sample.
  3. # Do not enter your integer like 4 352 764 or 4,352,764.
  4. # Enter it like 4352764.
  5. # Sampling 100000 times takes around 10 seconds.
  6. # It will return an Error after 5 minutes.
  7.  
  8. import sys
  9. sys.setExecutionLimit(300000)
  10. import random
  11. def sample():
  12. while True:
  13. x,y,z=sorted([random.random() for i in range(3)])
  14. s,a,b,c,d=0.5,x,y-x,z-y,1-z
  15. if (max(a,b,c,d)<s):
  16. area=((s-a)*(s-b)*(s-c)*(s-d))**0.5
  17. return area
  18.  
  19. samples=int(input("How many samples would you like? "))
  20. averageSample=sum([sample() for i in range(samples)])/samples
  21. print(averageSample)
This post has been edited 1 time. Last edited by goodbear, Mar 30, 2017, 2:54 AM
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
#5 • 2 Y
Y by Adventure10, Mango247
Note that as $n\to\infty,$ our answer should intuitively approach $\frac1{4\pi}$ as the best n-gon should approach a circle of circumference 1, and as it gets closer and closer to that circle, the expected area should be monotonically increasing. I think in general, the best polygon is cyclic.
This post has been edited 1 time. Last edited by goodbear, Mar 21, 2017, 5:33 PM
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
#6 • 4 Y
Y by v_Enhance, Derive_Foiler, centslordm, Adventure10
goodbear wrote:
I think in general, the best polygon is cyclic.

Actually, I just realized that following claim is true:

The polygon of largest area is cyclic.

Proof:
[asy]pair A=(6.8,9.8),
B=(7,7.3),
C=(9.6,5.4),
D=(12,4.8),
E=(16.4,6),
F=(19.2,8),
G=(19.4,10.8),
H=(15,13.2),
I=(10.2,12.6),
J=(7.8,11.2);
fill(A--B--C--cycle,lightgray);
fill(C--D--E--F--cycle,lightgray);
fill(F--G--H--I--cycle,lightgray);
fill(I--J--A--cycle,lightgray);
draw(A--B--C--D--E--F--G--H--I--J--A--I--F--C--A,black);[/asy]
Assume for the sake of contradiction that there was a non-cyclic polygon that had the optimal area with fixed side lengths. Obviously it would be convex. Then, some quadrilateral which has vertices from the polygon would not be cyclic. Then, fixing the other parts of the polygon (corresponding to the shaded regions in the diagram) while adjusting the quadrilateral by fixing the side lengths and making it cyclic would increase the total area of the polygon - a contradiction. Therefore, the claim is true.
This post has been edited 1 time. Last edited by goodbear, Mar 21, 2017, 6:37 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
#7 • 4 Y
Y by v4913, HamstPan38825, Adventure10, Mango247
That's great :) so for all $n$-gons we just want to find the largest area of a cyclic one.
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
#8 • 1 Y
Y by Adventure10
v_Enhance wrote:
That's great :) so for all $n$-gons we just want to find the largest area of a cyclic one.

Unfortunately, integrating an area formula won't work for long. There are known polynomials whose roots are the areas of cyclic $n$-gons for $n\le8,$ but they get much harder with each step.
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 • 3 Y
Y by v4913, HamstPan38825, Adventure10
Yeah, I agree it probably won't work for sufficiently large $n$. But at least we can get a sense of what the answer is for a few small $n$, and maybe get some intuition for these cases or find a pattern.
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
#10 • 3 Y
Y by v_Enhance, Adventure10, Mango247
goodbear wrote:
v_Enhance wrote:
As usual, we could also get numerical estimates via code.

  1. # This program will sample a cyclic quadrilateral's area (with the broken stick distribution).
  2. # It will ask you to enter how many times you want to sample.
  3. # Do not enter your integer like 4 352 764 or 4,352,764.
  4. # Enter it like 4352764.
  5. # Sampling 100000 times takes around 10 seconds.
  6. # It will return an Error after 5 minutes.
  7.  
  8. import sys
  9. sys.setExecutionLimit(300000)
  10. import random
  11. def sample():
  12. while True:
  13. x,y,z=sorted([random.random() for i in range(3)])
  14. s,a,b,c,d=0.5,x,y-x,z-y,1-z
  15. if (max(a,b,c,d)<s):
  16. area=((s-a)*(s-b)*(s-c)*(s-d))**0.5
  17. return area
  18.  
  19. samples=int(input("How many samples would you like? "))
  20. averageSample=sum([sample() for i in range(samples)])/samples
  21. print(averageSample)

According to this, under 2,000,000 tries, the expected value is about 0.04004.
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
#11 • 2 Y
Y by Adventure10, Mango247
Ran it for 5 million, output was 0.0400521326333.

Edit: 20 million gave 0.040042790940807815

Can we measure its precision?
This post has been edited 1 time. Last edited by j___d, Mar 31, 2017, 11:02 PM
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
#12 • 3 Y
Y by RadioActive, Goobersmith, Adventure10
Let the breaking points be $x \le y \le z.$ WLOG, assume that $y \le \frac 1 2;$ then we can set up the integral to be

\begin{align*}
&~ \frac{\int_{0}^{0.5} \int_0^y \int_{0.5}^{y+0.5} \sqrt{(0.5 - x)(0.5-y+x)(0.5-z+y)(z-0.5)} \, \mathrm dz \, \mathrm  dx \, \mathrm dy}{\int_{0}^{0.5} \int_0^y \int_{0.5}^{y+0.5} 1 \, \mathrm dz \, \mathrm  dx \, \mathrm dy} \\ \\
=&~ \frac{\int_{0}^{0.5} \int_0^y \int_{0.5}^{y+0.5} \sqrt{(0.5 - x)(0.5-y+x)(0.5-z+y)(z-0.5)} \, \mathrm dz \, \mathrm  dx \, \mathrm dy}{\frac 1 {24}} \\ \\
=&~ 24 \int_{0}^{0.5} \int_0^y \int_{0.5}^{y+0.5} \sqrt{(0.5 - x)(0.5-y+x)(0.5-z+y)(z-0.5)} \, \mathrm dz \, \mathrm  dx \, \mathrm dy.
\end{align*}
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
RadioActive
2302 posts
#16 • 1 Y
Y by Adventure10
Nice job. That looks good to me.
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
#17 • 2 Y
Y by goodbear, Adventure10
After an hour of painful algebra I got this:
$I=\frac{17\pi}{525}-\frac{\pi ^2}{160}\approx 0.0400427$
So it seems it's indeed correct (matches with 7 digit accuracy using 20 million in your code).
This post has been edited 5 times. Last edited by j___d, Apr 2, 2017, 1:41 AM
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
#18 • 2 Y
Y by Adventure10, Mango247
goodbear wrote:
Let the breaking points be $x \le y \le z.$ WLOG, assume that $y \le \frac 1 2;$ then we can set up the integral to be

\begin{align*}
&~ \frac{\int_{0}^{0.5} \int_0^y \int_{0.5}^{y+0.5} \sqrt{(0.5 - x)(0.5-y+x)(0.5-z+y)(z-0.5)} \, \mathrm dz \, \mathrm  dx \, \mathrm dy}{\int_{0}^{0.5} \int_0^y \int_{0.5}^{y+0.5} 1 \, \mathrm dz \, \mathrm  dx \, \mathrm dy} \\ \\
=&~ \frac{\int_{0}^{0.5} \int_0^y \int_{0.5}^{y+0.5} \sqrt{(0.5 - x)(0.5-y+x)(0.5-z+y)(z-0.5)} \, \mathrm dz \, \mathrm  dx \, \mathrm dy}{\frac 1 {24}} \\ \\
=&~ 24 \int_{0}^{0.5} \int_0^y \int_{0.5}^{y+0.5} \sqrt{(0.5 - x)(0.5-y+x)(0.5-z+y)(z-0.5)} \, \mathrm dz \, \mathrm  dx \, \mathrm dy.
\end{align*}
j___d wrote:
After an hour of painful algebra I got this:
$I=\frac{17\pi}{525}-\frac{\pi ^2}{160}\approx 0.0400427$
So it seems it's indeed correct (matches with 7 digit accuracy using 20 million in your code).

So we have the answer for $n=4.$ For $n=5,$ even though the area squared satisfies a 7th-degree polynomial, there is no definite area formula, and no clear pattern emerges between $\frac{\pi}{105}$ and $\frac{17\pi}{525}-\frac{\pi^2}{160}.$
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
#19 • 4 Y
Y by v4913, HamstPan38825, Adventure10, Mango247
j___d wrote:
After an hour of painful algebra I got this:
$I=\frac{17\pi}{525}-\frac{\pi ^2}{160}\approx 0.0400427$
So it seems it's indeed correct (matches with 7 digit accuracy using 20 million in your code).

Whenever you can, would you mind writing this up or outlining how to do it? I imagine not everyone knows how to evaluate that integral even in principle :P
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
#21 • 2 Y
Y by Adventure10, Mango247
Alright, done.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
MACISCO
2 posts
#22 • 2 Y
Y by Adventure10, Mango247
Excuse me.. I'm student in high school and I'm trying to solve this problem. I thought that regular polygon is the biggest in n-degree polygon. Is these discussion have premise that regular polygon is the biggest? I think we can start solving this problem by assuming that 'regular polygon is the biggest' and show every case of transform makes smaller polygon. I'm just a student and I don't have plenty of knowledge. Please advise me if I'm thinking wrong.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
hiabc
919 posts
#23 • 2 Y
Y by v_Enhance, Adventure10
This question does not ask, "What is the largest possible area of an $n$-gon with perimeter 1?" Instead, we want to find the expected maximum area.

This means that the stick of length 1 is randomly broken into $n$ segments. Assuming these segments can form an $n$-gon, what is the expected area of the $n$-gon, provided that it is maximized?

We have shown that the maximum is achieved when the polygon is cyclic (see my post here and goodbear's post here for the full proof). Additionally, if the segments can form a polygon, it is always possible to construct the polygon in such a way that it is cyclic.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
MACISCO
2 posts
#24 • 2 Y
Y by Adventure10, Mango247
I see... Thank you for your friendly answer. Then, it may be more complex question to us. I will reference yours and try to understand what you did and the way you approach to your solution. And also, I want to make my own solution about this if then, I'm looking foward to your simple checking :D Thank you again for your nice advice :)
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
hiabc
919 posts
#25 • 1 Y
Y by Adventure10
@MACISCO: No problem! Yes, I agree that it is quite a complex problem, but that's what makes it fun, no? :-D If you do find a solution, feel free to post it in this thread or use the V button by problem 1 and post a solution.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
h369a
1 post
#26 • 1 Y
Y by Adventure10
In @goodbear 's solution to expected area for $n=4$, the lower limit for the integral with respect to $x$ is $0$. But since $y-x<\frac{1}{2}$, why is the lower limit not $y-\frac{1}{2}$?. Setting up the integral this way obviously leads to a wrong answer, but I'm not sure why. I'm trying to clear up any confusion I have before I tackle $n=5$ and higher, so any help would be appreciated.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Derive_Foiler
2782 posts
#27 • 2 Y
Y by Adventure10, Mango247
Can we embed this in the complex plane? I was considering choosing the angles for the pentagon (or $n$-gon) and then scaling the pentagon by adjusting the circumradius until it gives $P=1.$ I got the area is this ugly thing, but no promises for accuracy. (I sort of work through it in this Desmos page. I can elaborate more if necessary.)

However, I feel like choosing the angles first may give a different distribution than choosing the sides first . . . is that true? (Is it fixable?)
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
#28 • 4 Y
Y by v4913, HamstPan38825, Adventure10, Mango247
Derive_Foiler wrote:
However, I feel like choosing the angles first may give a different distribution than choosing the sides first . . . is that true? (Is it fixable?)
I hink the distribution would definitely be different. Even in the triangle case, selecting the angles in the natural way over $\alpha + \beta + \gamma = \pi$ would give sides in the ratio $\sin\alpha : \sin\beta : \sin\gamma$ which won't be the same distribution of $a+b+c=1$ with $a,b,c \in (0,\frac12)$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Derive_Foiler
2782 posts
#29 • 1 Y
Y by Adventure10
Yeah, I was afraid of that. But anyways, I have an angle-oriented approach that I'm not sure how to fix so that the distribution matches. Here is something.

But anyways, I don't think we're going to find a direct formula for the area because other sources have only found that seven-degree polynomial, so I'd be surprised if we can do better than that (for the general case). Some thoughts.

I don't know; maybe someone will find this useful.
This post has been edited 1 time. Last edited by Derive_Foiler, Nov 5, 2017, 2:09 PM
Reason: redundant thought
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
#30 • 2 Y
Y by Adventure10, Mango247
For n > 4, wouldn't the answer be the sum of the side lengths divided by n? If you have side lengths 1,2,3,4 and 5, another shape would have side lengths of 5,4,3,2 and 1. They cancel each other out. The only shape that doesn't have an inverse is the one in the exact middle, the shape where all side lengths are the same length. To find the shape with all side lengths equal, you would need to find the sum of the side lengths and divide it by the number of sides. Please correct me if I'm wrong, I'm pretty sure I'm thinking too simply.
Z K Y
N Quick Reply
G
H
=
Page Feed | J
Linked Item Topics
G
Topic
First Poster
Last Poster
H
Problem(ii) Possible Solution Path
mathcrazymj   25
N Nov 24, 2018 by Nirmay
Look at my solution to problem 5 in this pdf: http://submissions.usamts.org/Year28/Round1/34279-1476743929-USAMTS%202016%20Matthew%20Roth.pdf

I found some useful results about cyclic quadrilaterals that may generalize to Problem(ii)

EDIT: I'll think about it some more but I think this problem can be solved by breaking n-gons into a bunch of quadrilaterals and maybe 1 triangle (depending on n) and maximizing the areas by making all the quadrilaterals cyclic and the triangle equilateral
25 replies
mathcrazymj
Mar 1, 2017
Nirmay
Nov 24, 2018
J
H
Expected Number of Intersections in Square
adamodoherty   0
Oct 25, 2017
Here is a new problem which ended up being a lot easier than I expected.

One of the lines connects to an opposite side of the square, during which case there is a $0.5$ probability that the lines will intersect. The probability of this occurring is $5/9$.

The lines connect sides which are connected to their original point. This occurs with probability $4/9$. In $1/3$ of cases they will share at least one side leaving a $0.5$ probability of intersection. The remaining $1/9$ of the time they will have no side in common and will have no chance of intersecting.

This yields $(1/2)(8/9)=4/9$.

This is the case for any two lines and therefore can be applied to all lines within the square. The probability is expected number of intersections for $n$ lines is just then the probability for two lines ($4/9$), multiplied by the number of combinations, ${n(n-1)/2}$.

So for example for the case of $n=74$ the expected number of intersections is $1200.4$.
0 replies
adamodoherty
Oct 25, 2017
0 replies
J
H
Some New Problems We Could Work On
adamodoherty   21
N Oct 1, 2017 by adamodoherty
Here are some new problems which I or other people could work on:

Problem 1

You are betting in a casino and you have to pay one dollar to play the game and you get thirty dollars if you win. In the casino game the casino breaks two sticks into three pieces each. The only way to win is to have the sum of your triangles area be greater than or equal to $x$. What is the probability you win? What is the lowest $x$ at which you will win more often that you lose?

Problem 2

Let's quantize the problem, something I don't think anyone has done yet. We break a stick into three pieces randomly with each break only having the possibility of being an integer between $ 0$ and $ 100$. Take the longest of the three pieces and stop when the sum of the longest pieces are a prime number. What is the expected value of the number of breaks you'll take? What is the probability you stop after $x$ breaks?

Problem 3

What about an expansion of the problem into three dimensions or more? What is the probability that after $x$ breaks a 3-dimensional quadrilateral can be formed?
21 replies
adamodoherty
Jun 26, 2017
adamodoherty
Oct 1, 2017
J
H
A New Problem
adamodoherty   18
N Sep 21, 2017 by adamodoherty
This is a new problem I've been thinking about for a while now, namely: what is the probability that an $x$-gon can be formed from $n$ breaks.

We already have the probability that with $n$ breaks an $n$-gon can be formed, via D'Andrea, $1 - \frac{n}{2^{n-1}}$. We also have the probability that a triangle can be formed from $n$ breaks, $ 1 - \prod_{k+2}^{n}  k/(F_{k+2} - 1) $ where $F_k$ is the $k$th Fibonacci number.

My problem is then investigating and attempting to find a general formula for determining the probability that a quadrilateral can be formed from $n=7$ for example.

The main point in determining if an $x$-gon (where $x$ is any number besides $n$) can be formed is making sure the $n$ breaks satisfy the inequality:

$s_1 + s_2 + s_3....+ s_{n-1} > s_l$

Where $s_l$ is the longest side, this is obviously just the extension of the triangle inequality theorem. This inequality obviously varies depending on what we want to find, for example solving for six breaks and a quadrilateral we need to make sure that of the $\binom6 4=15$ possible quadruples we could choose in at least one of them the sum of the three shorter sides are longer than the longest side.

A big factor in determining whether or not an $n$-gon can be formed is determining whether or not the stick has a break which is greater in length than $0.5$. The probability that an $n$-gon can be formed is simply $1 - \frac{n}{2^{n-1}}$, we can easily determine using arcs of a circle that the probability of a stick being greater in length than 0.5 is $\frac{n}{2^{n-1}}$.

If we break the stick into $n$ pieces by making $n-1$ breaks we get the probability of all breaks being less than or equal to some length $x$ to be $$
1-\sum_{v=0}^n (-1)^v {n\choose v}\left(1-v\frac{x}{t}\right)^{n-1}_{+}=\sum_{v=1}^n (-1)^{v+1} {n\choose v}\left(1-v\frac{x}{t}\right)^{n-1}_{+}.
$$
Where $x$ is the length which we cannot exceed, $n$ is the number of subintervals which we have and $t$ is the length of the interval (which for the rest of the post I wrote as simply being $1$).

The part I'm struggling with here is how to validate that $n$ breaks will be able to form an $x$-gon just from the lengths. That is to say I can't think of a good rule which will necessarily determine that an $x$-gon can be formed. Does anyone have any ideas?
18 replies
adamodoherty
May 12, 2017
adamodoherty
Sep 21, 2017
J
H
Random Lines Problem for Circles
adamodoherty   4
N Sep 15, 2017 by adamodoherty
What happens if we start applying the random line problem to circles? What about doing random lines within the triangle? How do things change?

Here are some questions which might be interesting:

What is the expected value of the largest piece of circumference between lines on the circle?

What is the expected area of the triangle which is formed from randomly selecting three points from within the circle (the answer for the unit square is $11/144$ as found in http://people.missouristate.edu/lesreid/AdvSol41.html)?

What is the probability after $n$ lines that two lines intersect? What is the expected number of intersections?

Just some ideas, we should continue work on the problem for the square but these might be a nice break from the square distribution.
4 replies
adamodoherty
Sep 5, 2017
adamodoherty
Sep 15, 2017
J
H
Expected Area after Lines
adamodoherty   0
Aug 26, 2017
What is the expected area after $n$ lines with the random line distribution is another question I've been thinking about lately.

Here is the value for $n=1$ I think, the lower values of $n=2,3$ could probably be reached using a similar method but this problem obviously becomes a lot more difficult as $n$ gets higher.

We start by choosing a side and then move to another side with each side being chosen with probability $1/3$. The largest possible area is $1-(x_1)(x_2)/2$, this is obvious on the other two sides because a connection will form a right triangle.

From here we can deduce that ${1 \over 3} \int\limits_{x_1=0}^1 \int\limits_{x_2=0}^1 (1 - x_1 x_2/2)\ dx_1\ dx_2 
+ {1 \over 3} \int\limits_{x_1=0}^1 \int\limits_{x_2=0}^1 (1 - x_1 x_2/2)\ dx_1\ dx_2 $ which is going to be equal to $(7/8)$.

We just need to figure out how to find the expected area when the line is connected to the side which sits opposite the side we have chosen.

This case is different because either side could be the bigger area. We therefore say that the area is {1 \over 2} |x_2-x_1| + x_1. Our area therefore becomes ${1 \over 3} \int\limits_{x_1=0}^1 \int\limits_{x_2=0}^1 {1 \over 2} |x_2-x_1| + x_1) dx_1 dx_2$ which is equal to $2/3$ expected value, below the $7/8$ of the other two.

The expected area therefore is $(7/24) + (7/24) + (2/9) = 29/36$, after the first line.

Does anybody see a method to work on this problem for higher values of $n$?
0 replies
adamodoherty
Aug 26, 2017
0 replies
J
H
Another Brand New Problem
adamodoherty   1
N Aug 26, 2017 by adamodoherty
It's not the best method but it's just an idea I had to perhaps get an estimate on the following question:

In the random lines within unit square problem what is the expected value of the largest piece of perimeter after $n$ random lines.

The method I have is somewhat crude, and we could probably come up with a general one which works better using code but it's what I have for now and it will give us an approximation.

For starters I think the best way to estimate the longest piece of perimeter in the unit square is by finding the expected value of the lowest side getting interrupted by a random line and the perimeter therefore being made less. If we can find the lowest expected value for $n$ we could come up with a reasonably good estimate.

It's actually been quite hard to figure out thus far, the best method I can think of is finding the probability that at least one side is interfered with zero times, the probability that at least one side is interfered with only one time, etc using Markov chains. For example:

Note that every side has a $(1/2)^n$ probability of being interacted with after $n$ random lines. At the first line two of the four sides are interacted, the other two have the potential to be avoided. There are three cases for the next line, it can intersect both the unintersected lines ($p=1/6$), it can intersect both the original lines ($1/6$) or it can intersect one new line and one old line ($2/3$).

This brings us to the case in which three sides have been interacted in which case there is a $1/2$ probability that our last remaining side will be destroyed.

Once you have these probabilities it's actually not all that difficult to tabulate the probabilities, it's just tedious (seems to be a normal Markov chain so we could use matrices and/or simulation to accomplish this more easily).

We get $5/6$ for $n=2$, $102/216$ for $n=3$, and $318/1296$ for $n=4$ and so on.

We can continue using the same method for the stick of the interruption of one.

This is just an idea of a method which is pretty basic mathematically but would probably require computer simulation to accomplish in full. I'll post a decent estimation of $n=2$ below.
1 reply
adamodoherty
Aug 26, 2017
adamodoherty
Aug 26, 2017
J
H
The New Case of [1,n]
adamodoherty   0
Aug 1, 2017
Here's an idea which might help shake things up a little bit: what about instead of focusing on breaking a stick of length $n$ into $x$ pieces we could instead take $x$ pieces randomly from the domain $[1,n]$. In the first case the $$\sum_{n=1}^{x} p_n = n$$and in the second case the result does not necessarily sum to $n$ (it is between $x$ and $xn$).

Let's look at the case where we have three pieces (note that in the version I do right now I use only the integers within $[1,n]$), what is the probability that a triangle can be formed.

What's more than finding the probability that some $x_1 + x_2 > x_3$ is finding some $x_1 + x_2 \geq x_3$. We focus on three cases $x_1=x_2$, $x_1<x_2$, and the case $x_2>x_1$ which should work for every case. The sum then that any combination of $x_1, x_2, x_3$. The new sum reduces I think to

$\sum_{x_1=1}^n \sum_{x_2=1}^{n} \frac{ \min(n,x_2+x_1) - \max(1,|x_1-x_2|) + 1}{n^3}$.

The probability of a triangle being formed under these new rules is then (trying to figure this out by $ p = \frac{1}{2} + \frac{3n-2}{2 n^2}$. So for example for $n=5$ the result is $19/25$ and for $n=10$ the result is $16/25$.

There are definitely a lot more interesting places to go with this question and some of the problems we've been working on can apply easily to the $[1,n]$ case.
0 replies
adamodoherty
Aug 1, 2017
0 replies
J
H
Variation of Problem 1
RadioActive   13
N Apr 9, 2017 by goodbear
Here's a variation to problem 1:

1. a) Given that the pieces form an acute triangle, what is the expected value of its area?
b) Given that the pieces form a right triangle, what is the expected value of its area?
c) Given that the pieces form an obtuse triangle, what is the expected value of its area?

Has this been solved before?
13 replies
RadioActive
Apr 6, 2017
goodbear
Apr 9, 2017
J
H
Literature Review Reveals Possible Solution
IdanCarre   5
N Apr 8, 2017 by v_Enhance
Hi, I'm Margaret (I go by Idan Carre here) I'm a college student at the College of Wooster. I saw this problem and played with it for a few hours. Here's what I've found:

There's a generalization of the solution for this problem using a stick of length 2s in An introduction to Geometrical Probability by A. M. Mathai. I have worked through most of the proof and it makes sense for the most part. The really short thumbnail sketch of the proof can be found here

https://books.google.com/books?id=FV6XncZgfcwC&pg=PA269&lpg=PA269&dq=Given+that+the+three+segments+form+a+triangle,+what+is+the+expected+value+of+the+area?&source=bl&ots=94f09IhijI&sig=5L78e2hpskFQs6Cp3KI4sHFaL-E&hl=en&sa=X&ved=0ahUKEwjrhviJn4HSAhVH5YMKHVu_DDgQ6AEILTAD#v=onepage&q=Given%20that%20the%20three%20segments%20form%20a%20triangle%2C%20what%20is%20the%20expected%20value%20of%20the%20area%3F&f=false

In the conclusion of Mathai's proof, the expected area is calculated to be $\frac{4\pi}{105}s^2$. In the case of the unit stick, $2s=1$ and $s=1/2$, so the expected value of the area in the case of the the unit stick is $\frac{4\pi}{105}(\frac{1}{2})^2 = \frac{\pi}{105}$

I will gladly provide a very detailed proof with better explanation than is given in the textbook I found if this is of any interested to anyone (I'm writing up all my work/results for this GroupMath thing in a separate latex document for my own reference).

The only source of confusion for me at this point is determining exactly where the double integral equation for the expected value of area comes from . It seems like Mathai is saying
\[
E(A)=\frac{\int \int Adx dy}{\int \int dxdy}
\]I understand how Mathai got $\int \int dxdy=\frac{s^2}{2}$, but i don't really get where this whole equation for E(A) comes from. Is this just based on the definition of E(A) in general? I thought expected value was "the sum of all possible values each multiplied by the probability of its occurrence". So the expected value of the area of the triangle should be the sum of all the possible triangle areas formed divided by the probability of each of those triangles being formed. Not sure how that relates at all to the form of E(A) Mathai provided.

I don't know the protocol on posts in this project so let me know if there's a problem with this post.

_________EDIT_________
I just saw that someone else posted on problem 1 but it wasn't linked to the problem so I didn't see it. My bad! I'll leave this here temporarily while I still try to sort out the last part of the proof.
5 replies
IdanCarre
Feb 8, 2017
v_Enhance
Apr 8, 2017
J
H
J
H
Problem(ii) Possible Solution Path
mathcrazymj   25
N Nov 24, 2018 by Nirmay
Look at my solution to problem 5 in this pdf: http://submissions.usamts.org/Year28/Round1/34279-1476743929-USAMTS%202016%20Matthew%20Roth.pdf

I found some useful results about cyclic quadrilaterals that may generalize to Problem(ii)

EDIT: I'll think about it some more but I think this problem can be solved by breaking n-gons into a bunch of quadrilaterals and maybe 1 triangle (depending on n) and maximizing the areas by making all the quadrilaterals cyclic and the triangle equilateral
25 replies
mathcrazymj
Mar 1, 2017
Nirmay
Nov 24, 2018
J