As of October, 2016, Embarcadero is offering a free release
of Delphi (Delphi
10.1 Berlin Starter Edition ). There
are a few restrictions, but it is a welcome step toward making
more programmers aware of the joys of Delphi. They do say
"Offer may be withdrawn at any time", so don't delay if you want
to check it out. Please use the
link to let me know if the link stops working.
Support DFF - Shop
If you shop at Amazon anyway, consider using
this link. We receive a few cents from each purchase.
Support DFF - Donate
If you benefit from the website, in terms of
knowledge, entertainment value, or something otherwise useful,
consider making a donation via PayPal to help defray the
costs. (No PayPal account necessary to donate via credit
card.) Transaction is secure.
e-mail with your comments about this program (or anything else).
A stick is broken randomly into 3 pieces.
What is the probability that the pieces can be assembled into a
Background & Techniques
I ran across this problem in one of the early chapters of
"Mathematical Recreations and Essays", Ball and Coxeter, Dover
presented as a paradox. They describe it this way: " It is
possible to put the stick together into the shape of a triangle provided
the length of the longest piece is less than the sum of the other two
(Euclid - Book 1, Proposition 20), that is, provided the length of the
longest piece is less than 1/2 of the total length. But the
probability that a fragment of the stick shall be less than half of the
stick equals 1/2. Thus the probability that a triangle can be constructed
of out the the three pieces into which the stick is broken would
appear to be 1/2."
Or, try my rationale: Common sense says that the probability is 1/2 since when we make the first random cut,
one piece is longer than 1/2 the total length and the other piece
less than or equal to 1/2 the total length. When we randomly make the second cut, there is a 50-50 chance that we'll cut
the piece that is more than half the length of the stick. In that case, a triangle can
be formed no matter where we cut it . If we happen to cut the
shorter piece, then no triangle can
be formed no matter where it is. So the probability of forming a triangle
But common sense doesn't always guarantee a correct decision!
This program runs batches of 100,000 trials and accumulates the number that
would successfully create a triangle. As you might suspect by
average number of successes is not 50%. More a case of false
reasoning than a real paradox, but an interesting exercise in any case.
I added an option to run single trials and display the resulting
triangle if one is possible.
Run a few trials and try to explain the result. A separate
"Explanation" tab gives the correct reasoning.
I'll call this a Beginner's level program even though it exceeds our 50
lines of code limit - it has about 70 user written lines. But
there are two distinct parts - The first part of the code
cuts and tests whether they would form a triangle about 30
lines. This is incorporated in the MakeTriangle
function. The Make 100,000 Trials button calls MakeTriangle
100,000 times and counts how many created valid triangles.
The graphics portion (40 lines of code) calls MakeTriangle to make the cuts, but
then must actually determine the coordinates of the vertices in
draw the triangles. A Triangle
from 3 Lines page over in the Math section derives the equations
for calculating the coordinates.
August 28, 2011: A viewer recently browsed through the
source code for this program and asked about another strategy for cutting
the stick which I had coded but decided to comment out. Just for fun,
here's an update which discusses three other ways to "randomly" choose where
to make the two cuts. They all make the first cut randomly at any
point on the the stick. The differences are how to make the 2nd cut.
|Strategy 1 says to make the 2nd random cut on the shortest piece
resulting from the first cut. It is doomed to failure the longest
piece from the first cut will already be more than 1/2 stick length and
therefore guarantee that no triangle can be formed.|
|Strategy 2 chooses the longest piece resulting from the first cut. This
turns out to be a better strategy than the one originally presented.
This turn out to have better success rate than the original "Strategy
0", make two independent random cuts. I spent many hours finding
an analytical solution to support the experimental results for Strategy
2.. More about this later.|
|Strategy 3 randomly chooses which of the two previous strategies to
apply. That is, we'll randomly choose either the shortest or the
longest piece upon which to make the 2nd cut. As you might guess,
this is only half as successful as strategy 2 since, on average,
we will be choosing the short piece guaranteeing failure.|
For the best of these strategies, Strategy 2, we can
analytically verify the experimental results. In what follows, we assume
that the original length of the stick is 1 unit. We'll call the
initial cut P1, and we
can assume that the P1 is less than or equal to 0.5 (since
"without loss of generality" as the math guys say) if P1 is greater
than 0.5, we could simply turn the stick around or walk around to the other side of the table to
continue the analysis. We will reference the location of both cut
points (P1 and P2) to the left end of the stick, i.e. point Px
is Px units from the left end.
I claim (or perhaps discovered) that the probability of forming a triangle with P2, the second cut,
made randomly on the longer right hand stick piece,
is P1/(1-P1). In fact, a triangle is formed only if P2 lies between
0.5+P1. The probability of a random point lying with any band of length
a line of length N is L/N. In this case, that is P1/(1-P1).
Let's prove it by contradiction. First, assume that P2 is between
P1 and 0.5 and that we can
still form a triangle. . This implies that the rightmost piece
is of length 1-P2 is <0.5, otherwise we could not form a triangle. Since P2 is < 0.5
(by assumption), the length 1-P2
> 0.5, a contradiction
to the assumption that it is <= 0.5 in order to form a triangle.
On the other hand, assume that P2 is greater than 0.5+P1, then the left hand
piece produced by this cut is longer than the distance from P1 to 0.5+P1,
i.e. is greater than 0.5, again a contradiction. I guess we
also need to prove that for 0.5 <P2<.5+P1 that the segments produced
by the P2 cut are both less the 0.5 units long. The left hand segment
length is P2-P1 and P2<0.5+P1 so P2-P1<0.5 +P1 -P1 =
0.5. The right hand side length is 1-P2 and P2>0.5
so 1-P2 must be < 0.5.
Running/Exploring the Program
Suggestions for Further Explorations
August 28, 2011: Done!
There is another variation of the problem that
asks for the probability of forming a triangle if we make the cuts
sequentially, i.e. make the first cut, then randomly select one of those
pieces to make a second random cut. Surprisingly, at least to
me, the probabilities are not the same as the original problem.
|Original Date: August 6,
February 18, 2016