Treebeard's Homepage : Stumpers

Treebeard's Stumper Answer
1 November 2002

Fifteen Men on the Dead Man's Chest

Arrgh, there be fine pirates a' plenty at yesterday's Dunn Middle School Treasure Island Halloween party! Now me fifteen mateys be standing around this dead man's circular chest giving the evil eye between each pirate and every other. Ye can almost see the lines cut across that circle between those swabs! For fifteen pirates, how many lines connect them, and how many spaces be marked out there on the treasure chest? Avast me, ye need a boon? Start with two and three and then four poor souls and make your count to discover the secret keys, but don't heave-to too soon or ye be scuttled!

Here are 5 pirates giving each other the evil eye across the dead man's chest. That's easy. I count 10 lines and 16 regions. But what about 15 men (or any number) around that same circle?

It's fun talking like a pirate! See the funny Dave Barry column (8sep02) for inspiration and this Pirate Jargon page for vocabulary.

At Dunn Middle School, we all read Robert Louis Stevenson's Treasure Island last summer, and we just had our Treasure Island Halloween festival. We all made costumes based on the book, the kids created booths and activities, and we invited younger kids from nearby Family School. Last year we did the same with The Wizard of Oz. (I've heard rumors about reading Tom Sawyer next year, but I'm promoting Alice in Wonderland for the costume possibilities!) This was the perfect middle school Halloween activity. That's me in the photo with a wig and a few dozen old AOL Cds sewn to my shirt: "Arrgh, I be a music pirate!" (And I made sweet noise and rainbows, like a walking disco ball!)

Of course my stumper is really a problem in combinatorial geometry. How many chords can be drawn between 15 (or n) points on a circle, and how many regions do they define? There's no requirement that the points be equally spaced. In fact, you might miss a region if you do space the points equally since any three lines intersecting at a single point will obscure a potential region. Consider that a constraint.

Here are a few related stumpers:


There are 105 lines connecting all 15 pirates around a circle. You have to draw 14 lines for the first pirate, 13 more lines for the second, 12 more for the third, and so on. So the total is 14+13+12+...+1 = (14x15)/2 = 105 lines. The number of regions between all the lines is much harder to figure. The pattern starts 1, 2, 4, 8, 16, but then it continues 31, 57, 99, with 1,471 regions for all 15 pirates. We must generalize from patterns. But think of the turkey who expects food every day and then gets the axe for Thanksgiving. Trusting patterns is always dangerous!

Notes:

I gave this stumper to all my students at Dunn Middle School on Halloween day, when a "normal" science class seemed out of the question. The results on figuring the number of lines between 15 pirates were interesting: 8-6th graders, 9-7th graders, and 8-8th graders figured it out, about 1/3 of our school. Here's the honor roll, because I promised:

Travis, Scott, Chris, Katie C., Cody, Logan, Terri, Liz, Kalin, Kathyrn C., Bryan, Trevor, Abby, Clay, Ryan S., Drew, Arielle, Molly J., Samantha, Sam, Max, Brandon, Alenandria, Ryan H. Katie R.

Grade level does NOT matter with this stumper. Algebra is being pushed on ever-younger kids because it looks good on transcripts and state testing results. I'm sure many even-younger kids are ready for algebra, and it should be available for them. But if the kids don't already have some "math sense," I think this politically motivated push to advance math education will hurt more than it helps. A strong math topics / pre-algebra class on thinking and using math will help kids develop their math chops and keep them interested so they want to keep learning in high school and beyond.


"Fifteen men on a
dead man`s chest..."

While the kids were working on my stumper, I doodled the above sketch with marker pens on the white board in my classroom. It has a nice 3D look because of the crossing lines and my fading markers. But it's not worth trying to count the regions. You have to think it.

When you actually draw the figure with 15 (or fewer) points, it's pretty obvious that you first draw 14, then 13, then 12, etc. lines from successive points. One of those math tricks that every student should know is that the sum of the first n numbers is :

                  n x (n+1)
  1+2+3+4+...+n = ---------
                      2

So for n points around the circle, there are

                    (n-1) x (n-1+1)   (n-1) x n
  1+2+3+4+...+n-1 = --------------- = ---------
                          2               2

With n=15 pirates, that comes to 1+2+3+4+...+14 = (14x15)/2 = 105 lines.

I admit I became a little obsessed with this stumper, and I attacked it with kite string and nails, and then a QBASIC program. The stumper for me became whether I could complete the figure with nails and a single loop of string. These look like computer graphics, but they are really digital photos:

Here are 15 points around the circle, about a foot and a half across. I eyeballed the nails and intentionally placed them slightly off-kilter to show all the regions. I made this pattern with a single loop of string that returns to my starting nail. That's not possible with an even number of points.Try it with four points! I believe it's always possible with an odd number of points. Then I tried 45 nails (since 360°/45=8° per nail, an even number). That was hubris. It didn't work. I finally got to this place where I couldn't continue because there was no "next move" available despite missing links. I'm sure I skipped a loop earlier. I plan to add the missing strings, but the beautiful 3D archecture and integrity will still be wrong, and it will bug me.
  
 
With 45 nails, I tried to use my algorithm of always connecting to the next free clockwise nail. The algorithm is good,
but I'm sure I skipped a nail early on. The close-up 3D geometry of the weave is imperfect, but still beautiful! All
those strings wouldn't be perfectly interlaced even if I did it right. Play with my QBasic Chord program to see why.
  
 
I made these computer images of 15 and 45 points with my CHORD.BAS program, coloring each
circle chord by its length. They are nice mandalas, but they don't have the 3D texture of real string art.
  
 
I think it's remarkable how much the computer image on the right (with 30 points) looks like the digital photo of my string art above (top right, with 45 points). Sure, it's more perfect, but I don't think it's better. It doesn't have the exquisite 3D weaving and side views of the real thing.




Is it my imagination, or is that a tiny Mandelbrot Set lurking in the center just like Palmer Eldritch! And look at the other computer image just above. Why?

All the DMS kids who "got it" with the number of lines fell for the classic 2n trap on counting the regions between the lines. The series starts promising, but it takes a turn with n=6:

n = 123456789101112131415
regions 12481631579916325638656279410931471

The method of finite differences is a useful general way to find a formula to fit a sequence. Begin by writing the sequence in a row. Then make another row with the differences between the numbers above it, and another row with the differences of the differences. Continue until you get a row that is a constant value:

  sequence           1       2      4      8      16      31      57      99      163
  first difference       1       2      4      8      15      26      42      64
  second difference          1      2      4       7      11      16      22
  third difference               1      2      3       4       5       6
  fourth difference                  1     1       1       1       1       1
The constant difference in the fourth difference row is the signal that we have a fourth power polynomial of the form:
  count = an4 + bn3 + cn2 + dn + e.
Finding the values for a, b, c, d, and e takes a bit of algebra. First compute the value of the polynomial for n=1, 2, 3, etc.
  n=1     a+b+c+d+e
  n=2     16a+8b+4c+2d+e
  n=3     81a+27b+9c+3d+e
  n=4     256a+64b+16c+4d+e
  n=5     625a+125b+25c+5d+e
  n=6     1296a+216b+36c+6d+e
Now build a difference table between these expressions:
  a+b+c+d+e   16a+8b+4c+2d+e   81a+27b+9c+3d+e   256a+64b+16c+4d+e   625a+125b+25c+5d+e   1296a+216b+36c+6d+e
      15a+7b+3c+d   65a+19b+5c+d        175a+37b+7c+d       369a+61b+9c+d        671a+91b+11c+d
              50a+12b+2c      110a+18b+2c          194a+24b+2c          302a+30b+2c
                        60a+6b             84a+6b              108a+6b
                                  24a                 24a
Now look back at our original difference table and notice that the constant difference in the last row was all 1, and also notice that each row begins with a 1. That's all we need to solve this equation with 5 unknowns:
                           1                                      1
  24a = 1,         so  a = --                               a =   --
                           24                                     24

                               60     36                          6
  60a+6b = 1,      so 6b = 1 - -- = - --                    b = - --
                               24     24                          24

                               50   72   46                       23
  50a+12b+2c = 1,  so 2c = 1 - -- + -- = --                 c =   --
                               24   24   24                       24

                               15   42   69     18                18
  15a+7b+3c+d = 1,  so d = 1 - -- + -- - -- = - --          d = - --
                               24   24   24     24                24

                               1    6    23   18   24             24
  a+b+c+d+e = 1,    so e = 1 - -- + -- - -- + -- = --       e =   --
                               24   24   24   24   24             24   

This math is tedious but not hard. This is a completely general method that will work with difference tables of any size and polynomials of any degree. In our case, plugging in the coefficients gives the formula:
                      1
  number of regions = -- (n4 - 6n3 + 23n2 - 18n + 24)
                      24
Here's a graph comparing this quartic polynomial with the function 2n-1 that shows how deceptive this stumper really is.

Above n=6, the two functions diverge rapidly. It's a good example of philosopher Alfred North Whitehead's advice to "Seek simplicity and distrust it."

Building a difference table is reminiscent of Pascal's Triangle, where each number is the sum of the numbers above. Indeed there is a connection:

  n    sum to /                                 sum row
 --------------                                 -------
  1    1                     1                        1
  2    2                   1   1                      2 
  3    4                 1   2   1                    4
  4    8               1   3   3   1                  8
  5    16            1   4   6   4   1 /             16
  6    31          1   5  10   10  5  /   1          32
  7    57        1   6  15  20   15  /  6   1        64
  8    99      1   7  21  35   35   / 21  7   1     128
                                   /
By removing the slice of Pascal's Triangle to the right of the diagonal, the sum of the remaining five numbers to the left in each row gives the answer to my stumper. The sum of the entire row gives the power of two that we first thought were the answers. Aha, so it's no surprise that the first 5 values are the same for each function!

The numbers in Pascal's Triangle conveniently gives the value of n choose r, the number of unique ways that r items can be selected from n things when order doesn't matter. The proper way to write this is like this , but that's too hard with HTML text, and there are alternatives.

                                 n!                              
  n choose r = nCr = C(n,r) = --------  where n! = "n factorial" = 1*2*3*...*n
                              r!(n-r)!                     

The formula for the regions in a circle between n chords can also be expressed in "n choose r" form. (Note that Pascal's Triangle usually starts with row 0 not row 1 as I labeled it above. That's why "n-1" shows up here.)

  regions = C(n-1,0) + C(n-1,1) + C(n-1,2) + C(n-1,3) + C(n-1,4)
     
          = n + C(n,4) + C(n-1,2)

            1
          = -- (n4 - 6n3 + 23n2 - 18n + 24)
            24

                (n-1)(n-2)(n2-3n+12)
          = n + -------------------- 
                        24
I'll leave it as an exercise to prove that these really are all equivalent. (I know I really should exercise more!)

The All You Ever Wanted to Know About Pascal's Triangle and more page has this very cool pattern. This stumper uses Pascal's Triangle from both sides!

Image Points Segments Triangles Quadrilaterals Pentagons Hexagons Heptagons
1
21
331
4641
5101051
615201561
72135352171

Again I'm struck how one good stumper leads to another, and so many problems have deep connections. Whew, my head is spinning. Time for a walk!

Here are some Web links for your own research on this stumper:

Back to Stumper


Last modified .

Copyright © 2002 by Marc Kummel / mkummel@rain.org