The Broken Stick Experiment

I found several interesting video lectures at the BLOSSOMS Video Library. One in particular that I enjoyed is called The Broken Stick Experiment [Flash]. In it, Professor Richard Larson asks the seemingly simple question,

If you break a stick randomly in two places, what is the probability that you can form a triangle from the three pieces?

If one of the pieces is too long, then the other two can't meet to form the triangle.
The lecture is only 33 minutes, and Professor Larson builds up a very pretty geometric proof, so I won't spoil it by posting the answer here. I will provide code for a simulation, though (yes, this is still a programming blog). See if you can guess the answer before running the simulation or watching the video.

import java.util.Arrays;
import java.util.Random;

public class BrokenStick {

   public static void main(String[] args) {
       Random random = new Random();

       int trials = 10000;
       int triangles = 0;

       double[] breaks = new double[2];
       double[] sides = new double[3];

       for( int i=0; i < trials; ++i )
       {
           breaks[0] = random.nextDouble();
           breaks[1] = random.nextDouble();
           Arrays.sort(breaks);

           sides[0] = breaks[0];
           sides[1] = breaks[1] - breaks[0];
           sides[2] = 1.0 - breaks[1];
           Arrays.sort(sides);
          
           if( sides[2] < (sides[0] + sides[1]) )
           {
               triangles++;
           }
       }

       System.out.println("Triangles: " + triangles);
       System.out.println("Trials: " + trials);

       double p = (double)triangles / trials;
       System.out.println("Proportion: " + p);
   }
}

The simulation breaks 10,000 sticks each into three random pieces using Java's Random class to come up with random lengths. If the longest piece of broken stick is longer than the two remaining pieces, a triangle can't be formed. Ten-thousand trials should be enough to accurately estimate the proportion of triangles made from the broken sticks to two decimal places. How close was your guess?

Related:
The Broken Stick Revisited

Six Visual Proofs

1/4 + 1/16 + 1/64 + 1/256 + ... = 1/3

---

1/3 + 1/9 + 1/27 + 1/81 + ... = 1/2

---

1/2 + 1/4 + 1/8 + 1/16 + ... = 1

---

1 + 2 + 3 + ... + n = n * (n+1) / 2

---

1 + 3 + 5 + ... + (2n − 1) = n²

---

a² + b² = c²

---

Related posts:
Math visualization: (x + 1)²

Further reading:
Proof without Words: Exercises in Visual Thinking
Q.E.D.: Beauty in Mathematical Proof

Also, my thanks go out to fellow redditor cnk for improvements made to the 1/3 + 1/9 + 1/27 + 1/81 + ... = 1/2 graphic.

How many squares are there on a chess board?

A standard chess (or checker) board is an 8 x 8 grid, so how many squares are there in total? It's tempting to shout out "Sixty-four!" but I'm talking about squares of all sizes, from 1 x 1, and 2 x 2, all the way up to 8 x 8. Go ahead and see if you can count them.
I tried counting up all the 1 x 1 squares, then all the 2 x 2s and 3 x 3s, but this takes awhile, and eventually I lost count. This method also doesn't lend itself very favorably to a general solution to the question "How many squares in an N x N board?" What if N = 100? How about if N = 1000? We need a more systematic and general approach.

My usual opening strategy when I come across a problem like this is to "brute force" a few small instances of the problem and check to see if a pattern emerges. From the pattern I try to see if I can come up with a formula, either by deriving it myself or, more typically, by searching for one online. Let's see if that works here.

For a 0 x 0 board there is a total of 0 squares.

For a 1 x 1 board there is a total of 1 square.

For a 2 x 2 board there is a total of 5 squares.

For a 3 x 3 board there is a total of 14 squares. One large 3 x 3 square, four distinct 2 x 2 squares (pictured below), and nine small squares.

For a 4 x 4 board there is a total of 30 squares, one large 4 x 4 square, four distinct 3 x 3 squares, nine distinct 2 x 2 squares, and sixteen small squares.

I think that's probably enough, because at this point I'm already starting to see a pattern develop. The sequence 0, 1, 5, 14, 30... probably doesn't mean much to most people, and I'll admit it didn't mean much to me either, at first. But when I looked just a little bit deeper, I noticed something familiar. Look at the differences between each of the terms of the sequence.

1 - 0 = 1
5 - 1 = 4
14 - 5 = 9
30 - 14 = 16
...

All of the differences are perfect squares, so it looks like all you have to do to find the nth total in the sequence, is add n² to the previous total. This gives us the following recurrence relation:

f(n) = f(n - 1) + n²

We can use this relation to find out how many squares there are on an 8 x 8 chess board. Continuing on from where we left off:

f(5) = f(4) + 5²
f(5) = 30 + 25 = 55

f(6) = f(5) + 6²
f(6) = 55 + 36 = 91

f(7) = f(6) + 7²
f(7) = 91 + 49 = 140

f(8) = f(7) + 8²
f(8) = 140 + 64 = 204

But how do we confirm that? More importantly, what can you do if you didn't notice a pattern in the sequence in the first place? Searching Google for the sequence 0, 1, 5, 14, 30 gives surprisingly good results in this case, but it normally won't so I want to show you a better place to search. That better place is called the Online Encyclopedia of Integer Sequences. (If you've been spending time at any of the programming puzzle sites that I featured in my last post, you'll want to bookmark OEIS. It's a treasure trove of nerdy goodness.)

Searching OEIS for 0, 1, 5, 14, 30 turns up sequence A000330. That sequence starts out

0, 1, 5, 14, 30, 55, 91, 140, 204...

which definitely seems to confirm the answer we got above.

Scanning through the comments I noticed this one:

Gives number of squares formed from an n X n square...

which is exactly what we're looking for. Further down the page you'll find plenty of formulae, and even source code in several different programming languages, for calculating the terms of the sequence. For example, here's a closed form expression for calculating the nth term of the sequence:

f(n) = n * (n + 1) * (2 * n + 1) / 6

Solving for n = 8, we get

f(8) = 8 * (8 + 1) * (2 * 8 + 1) / 6
f(8) = 8 * 9 * 17 / 6
f(8) = 1224 / 6 = 204

which further confirms the answer we already knew.

If it seems like there are an awful lot of comments, formulae, and references on OEIS, that's because this particular sequence, the sum of the squares from 1 to n, turns up often in many areas of mathematics. Most of the sequences on OEIS won't have this much information to sift through, but you'll very often find something useful.

A Challenge

Now that you know a general strategy for solving puzzles involving integer sequences, why don't you give the following puzzle a try?

How many triangles (of all sizes) do you see in the equilateral triangle below?
Before counting triangles or searching online for the answer, see if you can build a sequence and find a pattern and a formula the way I did with the chess board problem above. Good luck!