Treebeard's Stumper Answer

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 heaveto 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:
 By lining up the points just so, what's the fewest number of regions you can define?
 I got the idea to make a string art copy of the solution with nails and kitestring. It's too awkward to tie every line separately, but is it possible to loop a single string around all 15 nails to show every line without going over the same line twice?
 What is the real origin of that great pirate song from the book:
Fifteen men on the dead man's chest 
Yohoho, and a bottle of rum!
Drink and the devil had done for the rest 
Yohoho, and a bottle of rum!
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: 86th graders, 97th graders, and 88th 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 everyounger kids because it looks good on transcripts and state testing results. I'm sure many evenyounger 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 / prealgebra 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 =  2So for n points around the circle, there are
(n1) x (n1+1) (n1) x n 1+2+3+4+...+n1 =  =  2 2With 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 offkilter 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 closeup 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.

All the DMS kids who "got it" with the number of lines fell for the classic 2^{n} trap on counting the regions between the lines. The series starts promising, but it takes a turn with n=6:
n = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 regions 1 2 4 8 16 31 57 99 163 256 386 562 794 1093 1471 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 1The constant difference in the fourth difference row is the signal that we have a fourth power polynomial of the form:count = an^{4} + bn^{3} + cn^{2} + 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+eNow 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 24aNow 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 24This 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 =  (n^{4}  6n^{3} + 23n^{2}  18n + 24) 24Here's a graph comparing this quartic polynomial with the function 2^{n1} 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!(nr)!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 "n1" shows up here.)
regions = C(n1,0) + C(n1,1) + C(n1,2) + C(n1,3) + C(n1,4) = n + C(n,4) + C(n1,2) 1 =  (n^{4}  6n^{3} + 23n^{2}  18n + 24) 24 (n1)(n2)(n^{2}3n+12) = n +  24I'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 2 1 3 3 1 4 6 4 1 5 10 10 5 1 6 15 20 15 6 1 7 21 35 35 21 7 1 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:
 I was looking for a halloween stumper that involved 15 men and a deadman's chest and maybe even a bottle of rum, and I finally found this one in John H. Conway and Richard K. Guy's The Book of Numbers (1996), pp. 7679. With some searching, I found it elsewhere too, e.g. Martin Gardner's Mathematical Circus (1992) and problem 47 in Yaglom's Challenging Mathematical Problems with Elementary Solutions, Vol. 1 (Dover,1987). It's known as Moser's circle (or spot) problem, and may have been first posed by Leo Moser in 1950. This stumper is discussed on the Web at MathWorld and Ask Dr. Math. The numbers are sequence A000127 at the OnLine Encyclopedia of Integer Sequences. There's a different approach to the solution at CutTheKnot. There are more stumpers with circle chords here and here. I have no idea what is the fewest number of regions you can define by lining up the points just so, except for the easy answer that there's just the one region if all points are on top of each other.
 Difference tables are a powerful tool for analyzing sequences of numbers that I never learned in school. I use them in my Christmas CutUps (14 Dec 01) to solve another stumper. There's some discussion here and here, and there's more discussion in this online textbook.
 There's info on string art at Line Designs, including a JAVA program that reminds me of my first computer. There are examples at John's String Art pages and lots of hits with a google search. The expensive but fun ZomeTools kits are the 3D equivalent. Jon Millington's book Curve Stitching: Art of Sewing Beautiful Mathematical Designs (1993) is a classic source.
 Arrgh, I almost forgot there be pirates in this stumper! This source (also here) tells the story:
Dead Man's Chest is part of the British Virgin Islands. In the early 1700s ... the pirate Edward Teach  known as "Blackbeard"  punished a mutinous crew by marooning them on Dead Man's Chest, an island 250 yards square surrounded by high cliffs and without water or landing places. Each was given a cutlass and a bottle of rum, and Teach's hope was that they would kill each other. But when he returned at the end of 30 days he found that 15 had survived.
 You can find Robert Louis Stevenson's Treasure Island on the Web. I love the intro poem, but I wonder how many of our DMS kids understood that elegant writing that's addressed to them. It's another stumper to pick the best movie version, and don't forget Captain Blood, The Sea Hawk, and Captain Kidd. I won't try to pick a movie, but I do pick A.L. LLoyd and Ewan MacColl's Blow Boys Blow for songs, and the great Patrick O'Brian books for more adventures at sea, and S. Clay Wilson's Checkered Demon underground comix are surely the ultimate overthetop twisted pirate tales, for "adults" only. You can find pirate accessories at The Pirate's Locker. See the funny Dave Barry column (8 sep 02) for inspiration and the Pirate Jargon page for vocabulary. You can discover your secret pirate name at fidius.org: "Arrgh, I be Mad Jack Cash!"
 I have many more stumbers on combinatorial geometry in the vault, including Christmas CutUps (14 Dec 01), Tricky Tetrahedra (26 Oct 01), Round Robin (9 Feb 01), FourColor Christmas (15 Dec 00), Olympic Number Rings (22 Sep 00), Holiday Magic (18 Dec 98), Chess Squares (15 May 98), Another Magic Star (19 Dec 97), and Magic Star (11 Dec 96).
Back to Stumper
Last modified .