Comments on Bill the Lizard: The Broken Stick Experiment

Sam152's solution is correct; it is the answer...

2010-11-30T11:42:38.862-05:00

Sam152's solution is correct; it is the answer the Spartacus's variant.

Bill's original problem statement was under-specified, admitting two interpretations that yield different answers. (Do you choose two cutpoints independently and uniformly on the original stick; or do you make one uniform random cut, and then make another uniform random cut on one of the pieces?)

See http://www.cut-the-knot.org/Curriculum/Probability/TriProbability.shtml

Spartacus, I've read about half-a-dozen variat...

2009-08-25T20:46:12.656-04:00

Spartacus,
I've read about half-a-dozen variations on this problem (mostly linked from the notes on the BLOSSOMS page) but I haven't seen that one. This might take a while. :)

1. Probability that both cuts are on opposite side...

2009-08-24T18:23:11.688-04:00

1. Probability that both cuts are on opposite sides of the midpoint: 1/2
2. Probability that two cuts on opposite sides of the midpoint are less than half the stick length apart: 1/2

Therefore the probability of forming a triangle is 1/2*1/2=1/4

Here is a more difficult problem with an even more surprising result: You break the stick into two pieces, then randomly choose one of the two pieces and break it into two pieces. What is the probability that the resulting three pieces can form a triangle?

You will be amazed by the solution!

(Hint: the answer is not just a simple fraction like the original problem; however there is a very nice closed form)

Bill the Lizard, I suspect most people would anti...

2009-08-21T19:17:19.538-04:00

Bill the Lizard,

I suspect most people would anticipate that having a consistent or particular stick length shouldn't matter here. What's at issue is where the two breaks appear, that is, relative to overall length. A million sticks all of different lengths and all randomly broken in two places should demonstrate the same probabilistic characteristics of a million sticks all of the same length because, again, what's at issue is relative in any event.

This principle can be demonstrated as follows. In my simulation each stick length is represented by T, that is, the sum of R1, R2 and R3. If I wanted/needed to ensure that each and every occurrence of T always comes out to equal a certain value, a few more columns could be inserted which accomplish this simply by adjusting the sizes of R1, R2 and R3 by some definitive amount. For example, if for one row T presented as equal to 16,000 [compared to, say, the value of 21,000 I'd predetermined as a uniform stick length], obviously all I'd have to do is increase each of the original random numbers by 21/16.

So even though now all million stick lengths are the same, the actual percentage of that length occupied by each R1, R2 and R3 hasn't changed at all. The outcome would still match the 50% probability that my simulation currently produces.

In short, Woe to The Foe, heh heh heh.

Here are the formulas I employ for...

...{R1,R2,R3}
................ =RANDBETWEEN(1,10001)

..........{T}
................ =SUM(E2:G2), because R1, R2 and R3 occupy columns E, F and G.

...{P1,P2,P3}
................ =E2/H2; =F2/H2; and =G2/H2, because T occupies column H.

.........{C1}
................ =IF((J2<0.5)*(K2<0.5)*(L2<0.5),1,0), because P1, P2 and P3 occupy columns J, K and L.

And fun was had by all.

Tom, The particular value of the stick length does...

2009-08-21T14:02:33.377-04:00

Tom,
The particular value of the stick length doesn't matter as much as making sure the three pieces add up to whatever length you decide on. I used a stick length of 1.0 in my similation, but it doesn't hurt anything if you choose a length of 10,000.

What really makes a difference is how you choose your random lengths. If you choose three random lengths then add them together, you don't really know the length of the stick you started with. If you start with a specific length, then make two random breaks within the boundaries of the stick, you're guaranteed to end up with three random lengths that add up to your original stick length.

It's possible that I just didn't correctly understand the explanation of your spreadsheet. Without seeing the formulas you used I can't be sure that this part of your simulation isn't correct. The errors you're getting could be from another part of the calculation, but this is the most logical place to start looking.

Bill the Lizard, I'll work this up and see wha...

2009-08-21T13:49:49.470-04:00

Bill the Lizard,
I'll work this up and see what gives. It's definitely counterintuitive though that always having the same stick length would even matter, that is, any more than it would matter that triangle of type Q presents as q1, q2, ...qn for n of any size. Be nice to hear the why behind your assertion. Maybe the lecture will help in this regard.

Tom, From your explanation it looks like you'r...

2009-08-21T09:55:14.584-04:00

Tom,
From your explanation it looks like you're generating three random lengths to represent the three pieces of stick. The problem with this approach is that there's nothing to make sure the three pieces all add up to the original length of the stick.

Try it by generating only 2 random numbers (x and y) that represent the break points. If 10,000 is the length of the original stick, and you pick 2 random numbers between 0 and 10,000 then the lengths of the three pieces will be x, y-x, and 10,000-y when x < y, or y, x-y, and 10,000-x when x > y. (It's easier if you just select two random numbers then sort them so x < y, then just always use x, y-x, and 10,000-y for the three lengths, which is essentially what I did in my code.)

I'll try to get my next post up this weekend. I have the answer to your question about acute and obtuse triangles, but proving why I'm getting the number I'm getting is proving to be a little bit complicated.

Bill the Lizard, Definitely courting tedium at thi...

2009-08-21T01:00:20.224-04:00

Bill the Lizard,
Definitely courting tedium at this point.

n R1 R2 R3 T P1 P2 P3 C1

These represent column headings in Excel.

R1, R2 and R3 denote random numbers using the RANDBETWEEN function; I chose for each number the range from 1 to 10,001.

T denotes the sum of R1, R2 and R3 for each row.

P1, P2 and P3 denote which percentage of T is entailed of R1, R2 and R3 respectively.

C1 (for condition 1) represents a check to see whether P1, P2 and P3 all three entail percentages less than 0.5, posting a 1 if they do and a 0 if they don't.

n denotes the number of iterations which, as I said, I took the time to set at 1 million.

Totaling the C1 column provides a sum which, divided into 1 million, quite closely approximates the probability that no 'leg of the triangle' will be greater than or equal to one half.

Additionally I generated a macro which recalculates the worksheet 100 times, posts each result to a table and then finds the average of that set.

You can imagine my surprise to hear that the actual probability varies significantly from what this arrangement points up.

I'll take a look at that lecture this weekend.

Tom, Check your simulation code against mine. You...

2009-08-19T08:29:23.349-04:00

Tom,
Check your simulation code against mine. Your answer is off by quite a bit more than just rounding error. You can post your code here, or on Stack Overflow if you'd like me to take a look at it (provided it's in a language I know reasonably well, Java, C, C++, Python, PHP, or any dialect of Basic).

Bill the Lizard, To follow up here, beginnings of...

2009-08-18T23:35:08.891-04:00

Bill the Lizard,

To follow up here, beginnings of a guess are as follows: For some small range [in the form of a difference], as two legs of the triangle both approach 1/2, the small difference between them cannot be bridged by the infinitesimally small remaining leg. Be nice to make a formal statement.

Bill the Lizard, So true. (I'm feeling better...

2009-08-18T22:59:50.266-04:00

Bill the Lizard,

So true. (I'm feeling better already.) After 100 simulations with n=1,000,000 I'm seeing slightly less than 50%. More specifically I'm seeing 49.994067% and am definitely curious as to what explains this slight deviation. I think I'd rather contemplate it for a while though, that is, to see if I can figure it out myself.

Tom, Close. "All it takes for the three piec...

2009-08-18T19:19:30.314-04:00

Tom,
Close. "All it takes for the three pieces to form a triangle is that none of the pieces have a length greater than or equal to 1/2 the length of the stick." This much is true, but that doesn't happen a full 50% of the time (which was also my initial guess before I watched the full lecture).

Bill the Lizard, Whoa, hey, no, it can't be a...

2009-08-18T18:40:54.551-04:00

Bill the Lizard,

Whoa, hey, no, it can't be as simple as that can it?

All it takes for the three pieces to form a triangle is that none of the pieces have a length greater than or equal to 1/2 the length of the stick. And that's a full 50% of the time.

What gives? I thought certainly the question would pose a greater challenge than that.

Tom, Disregard my last answer, as I had misunderst...

2009-08-17T21:31:49.007-04:00

Tom,
Disregard my last answer, as I had misunderstood your question. There are no constraints on what kind of triangle you can get (acute, obtuse, right, or no triangle at all) or on the order of the pieces. Any of the pieces can be the longest when you randomly select the two break-points. The only reason I sort the pieces in my code is because I need to know which piece is longest, so that I can tell if the pieces form a triangle or not. This has no impact on the final outcome.

Bill the Lizard, Gee, no I hadn't imagined th...

2009-08-17T21:06:35.980-04:00

Bill the Lizard,

Gee, no I hadn't imagined that the base of the triangle had to be the largest of the three pieces. All of these unstated parameters make it very difficult to approach the problem in a systematic way.

So far, yes, the triangle can be of any sort, the pieces can be moved around at will and, finally, (if I understand your last answer), the base of the triangle is expected to be whichever piece [of the stick] that's the longest.

Is this correct? Is there anything else in the way of allowances and/or limitations?

Tom, Any of the three sides could form the base (I...

2009-08-17T18:39:04.169-04:00

Tom,
Any of the three sides could form the base (I'm assuming by base you mean the longest side). In the code I gave you can see how I work around this by calculating the length of the three sides, then immediately sorting them (on line 24) so that I always know where the longest side ends up.

I'm working on an entire post to answer your other question. :)

Bill the Lizard, Good. If you limit outcomes to a...

2009-08-17T15:40:06.651-04:00

Bill the Lizard,

Good. If you limit outcomes to acute triangles, (including equilaterals), what probability do you get?

Oh, and another question [intended to confirm an assumption on my part]: Is this strictly an ordered set or can any of the three pieces form the base?

Tom, You could end up with an acute, obtuse, or (r...

2009-08-17T07:35:55.221-04:00

Tom,
You could end up with an acute, obtuse, or (rarely) equilateral triangle. You've got me curious now, so I'll have to modify the code later and run another simulation to see if acute or obtuse triangles are more common. Good question!

Bill the Lizard, Hi. Great question. There is on...

2009-08-17T03:20:09.546-04:00

Bill the Lizard,

Hi. Great question.

There is one thing I'm not clear on, though, from the description. Do obtuse triangles count here, or is the solution limited to acute?

fiberfiend6891, I appreciate the heads up. That l...

2009-08-08T09:46:57.756-04:00

fiberfiend6891,
I appreciate the heads up. That link is now fixed. Thanks for reading.

Just a heads up - the link directly to the video h...

2009-08-08T09:27:48.965-04:00

Just a heads up - the link directly to the video has http doubled and doesn't work when clicked directly (I had to copy/paste and get rid of the double):
http://http//blossoms.mit.edu/video/larson-watch.html

This is my first time seeing your blog, and I absolutely LOVE it!

Sam152, That's a little bit low; lower than ro...

2009-08-06T07:45:50.595-04:00

Sam152,
That's a little bit low; lower than rounding error would explain. Do you want to share your code? You could either post it here, or as a Stack Overflow question and I'd be happy to take a look.

Very interesting post, my nifty c++ program calcul...

2009-08-06T07:04:35.711-04:00

Very interesting post, my nifty c++ program calculated about 18.9% successes after 10,000 tries. How close is this?

tg, Now you have it! I like the approach you used...

2009-07-29T13:01:11.887-04:00

tg,
Now you have it! I like the approach you used because you're showing the exact opposite of what the problem asks for, the probability of NOT forming a triangle. This kind of thinking is a very powerful tool in mathematics, and is often overlooked.

B the L, you are a patient individual. One fina...

2009-07-29T12:00:23.200-04:00

B the L, you are a patient individual.

One final attempt to redeem myself. The "*" was supposed to be "+". The risks of writing at work.

We are looking for the Probability of (a>b+c) OR (b>a+c) OR (c>a+b).

a + b + c = L
P(a>b+c) = P(a>L/2)

For a>L/2, two breaks must occur on the right half:
P(of a break occurring on the right half) = 0.5
P(of two independent breaks occurring on the right)=
P(a>L/2) = 0.5*0.5 = 0.25

For b>L/2, two independent breaks must occur on either the left quarter, the right quarter, or both breaks on the left quarter, or both on the right quarter. The probability of ONE break landing on that 50% of the stick = 0.5. The probability of another break independently landing on the same 50%of the stick = 0.5*0.5 = 0.25.

c is the same as a, so
P(c>b+a) = P(a>b+c) = 0.25

For any one length > L/2 = (a>b+c) OR (b>a+c) OR (c>a+b) = 0.25+0.25+0.25.

If this is wrong, spare me the indignity and just delete my comments.

Appreciate your comments, didn't realize how lazy I'd gotten!