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
Finding the Minimum
j B k k N
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
RadioActive
2302 posts
#1 • 1 Y
This topic is linked to Problem 7.
Y by Adventure10
Instead of asking for the maximum number of triangles Alice can make, I think it might also be interesting if we ask for the minimum. What do you guys think?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
GeronimoStilton
1521 posts
#2 • 2 Y
Y by Adventure10, Mango247
If both Bob and Alice are trying to minimize, we let Alice split it into 1/4 and 3/4 lengths, then Bob splits similarly with the 1/4 length and creates 1/16 and 3/16 lengths, and so on with the shortest length getting split in $1:3$ proportions.

We claim that there are zero triangles at any point in this process. For the purpose of proof by contradiction, we suppose that there is some triangle created. Let the maximum length of this triangle created be $m$. We see that $m$ is of the form $\frac{3}{4^n}$ for some positive integer $n$ because if it was of the form $\frac{1}{4^n}$, the only other possibility, we would have that it was the least of all the lengths, which cannot be for the greatest length in a triangle. Clearly, none of the other lengths of the triangle have the same length, and so the two lesser lengths must both be less than or equal to $\frac{1}{4^n}$ where $m = \frac{3}{4^n}$ because otherwise they would be greater than or equal to $m$, which is clearly impossible. Therefore, $m \le \frac{1}{4^n} + \frac{1}{4^n} = \frac{m}{3} + \frac{m}{3} = \frac{2m}{3}$ by the Triangle Inequality, but this is impossible because $m$ is positive, and so we see that no triangles exist.
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
#4 • 2 Y
Y by v_Enhance, Adventure10
I think we should look at when Bob is working against Alice.
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 • 4 Y
Y by Toinfinity, v4913, HamstPan38825, Adventure10
I think this is a good variation! :) I agree we should focus on the case where Bob is working against Alice. Let me know if you get any preliminary results (even small $n$).

One thought is that it probably makes sense for Alice to break off pieces of small $\varepsilon$ length, since those are nearly impossible to use to form triangles. So I'd expect that Alice can cause relatively few triangles to be formed, but that's just a guess.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
GeronimoStilton
1521 posts
#6 • 3 Y
Y by v_Enhance, Adventure10, Mango247
On Bob's first turn, he can't guarantee any triangles, as Alice can just cut the stick into $1/2$ and $1/2$ lengths, and so whichever sticks are left after Bob's turn will create a degenerate triangle.
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
#7 • 2 Y
Y by v_Enhance, Adventure10
It's also 0 for 3 breaks. Let Alice break at $\frac{1}{2}$. WLOG, Bob breaks between $0$
and $\frac{1}{2}$. If Bob breaks at $\frac{1}{4}$, then Alice can break anywhere between $0$ and $\frac{1}{2}$. If Bob doesn't break at $\frac{1}{4}$, then Alice can break at $\frac{1}{4}$.
This post has been edited 2 times. Last edited by RadioActive, Dec 27, 2017, 12:49 AM
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
#8 • 3 Y
Y by v_Enhance, Adventure10, Mango247
For $4$ breaks, Bob should be able to create at least 3 triangles by breaking the largest piece on his second break into equal halves (he can form a triangle with the equal halves and any other piece), unless there exists more than one piece of the largest length.

Suppose there does exist more than one piece of the largest length. Before Bob's second break, let the pieces have lengths $x,y,z,z$, where $x<y<z$. Then Bob can break the piece with length $x$ (it doesn't matter how he breaks it). Let the new pieces be $x_1$ and $x_2$. There will be $3$ triangles from $z-z-x_1, z-z-x_2, z-z-y$.

So I think $3$ is a lower bound for $4$ breaks.
Z K Y
N Quick Reply
G
H
=
Page Feed | J
Linked Item Topics
G
Topic
First Poster
Last Poster
H
Question on Progress
mmaotmh   0
Sep 17, 2018
It appears to me that the thread you are looking at is using n as the number of breaks, but the question defines n as the number of pieces.
0 replies
mmaotmh
Sep 17, 2018
0 replies
J
H
A generalization of Problem 7
GeronimoStilton   0
Dec 29, 2017
$a+b$ players play the following game consisting of $n - 1$ turns. Alice's $a$ clones and Bob's $b$ clones go in some order. After all turns have passed, there are $n$ pieces. What is the maximum number of triangles that Alice's clones can guarantee forming given that Bob's clones are working against Alice's clones?

Clarification: One possible ordering might be $a_1,b_1,a_2,b_2,b_3$, which would repeat, and so for the first $6$ turns in this example, Alice's clones and Bob's clones would follow the sequence $a_1,b_1,a_2,b_2,b_3,a_1$.
0 replies
GeronimoStilton
Dec 29, 2017
0 replies
J
H
Finding the Minimum
RadioActive   6
N Dec 27, 2017 by RadioActive
Instead of asking for the maximum number of triangles Alice can make, I think it might also be interesting if we ask for the minimum. What do you guys think?
6 replies
RadioActive
Dec 14, 2017
RadioActive
Dec 27, 2017
J
H
Problem #7
RadioActive   18
N Nov 23, 2017 by RadioActive
Here are some small cases for #7:

2 breaks

3 breaks
18 replies
RadioActive
Mar 9, 2017
RadioActive
Nov 23, 2017
J
No more topics!