This is a story about how a simple puzzle ended up haunting me for over 20 years. It's a story of hubris blocked by a mountain of cold mathematics, and the obsession spawned by knowing an answer is out there, but not knowing how to find it.
Growing on a remote island, my youthful thirst for new reading material was quenched in regular bursts from the Scholastic catalogue, a thrilling piece of folded A3 paper that flaunted great collections of tremendously exciting tomes on everything from monsters to maths. The best were the ones that combined the two.
Popular at the time, these adventure books were printed RPGs that demanded you solve puzzles to advance through the story. To the best of my memory, the problem that proved so terrible to me started out like this:
James is given a lucky pendant from an old witch. On the charm are five points arranged in a circle, each connected to all the others, forming a five pointed star enclosed in a pentagon. The lucky charm will only work if the number of triangles that appear in this diagram is written into the centre of the star. How many triangles appear in the symbol?
Stand up mathematician Matt Parker has a good description of the puzzle here.
The puzzle is fairly easy to solve - there are seven different triangles in the symbol, and each is repeated five times through the shape (hooray for rotational symmetry!). So 7*5 is 35. After I solved that trifling little thing, my curious eight-year-old brain asked a follow-up question. The kind of naive question that, like many of the questions children dream up, is very simple to ask and extraordinarily difficult to answer. It's a question that I've been grappling with, on and off, for 20 years, and it's a question I still don't have an answer for. This is the question:
If 5 interconnected points make 35 triangles, how many triangles do n points create?
Of course, I didn't say it like that when I was 8, but I was interested to know what the relationship between the number of points and the number of triangles was. Little did I know how fiendishly difficult this would turn out to be.
The obvious thing to do was to solve the puzzle for more shapes. Four interconnected points creates a square with a cross through it, like a marked ballot paper. The triangles are easy to count - two kinds, repeated four times, so eight in total. For n=3 it's even easier, as three points form a single triangle.
In fact, I'd solved a very similar puzzle before, called the Mystic Rose. This is a straightforward little problem in which a number of points are arranged in a circle and then interconnected. With enough points, the resulting pattern looks a bit like a flower. The question is: how many lines are produced for a rose with 20 points? This is so easy an 8 year old could solve it: to interconnect 20 points, your first point needs 19 lines, the next one 18, then 17, then 16, and so forth.
In fact, I even knew a better way than laboriously adding numbers to solve that. This trick I learned from my third grade teacher (whose other major lesson, regrettably, was to demonstrate for us the connection between chain smoking and lung cancer). She once asked who could add together all the numbers from one to 100 the quickest. Being both cunning and lazy, I realised the fastest way was to discover the underlying pattern, which in this case is (n+1)*(n/2). You can see a good explanation of how this trick works here.
As a young child, I liked solving number patterns like there, and I had a simple technique for doing it. I would draw a grid with the numbers I had, like so:
| Number of points: | 3 | 4 | 5 |
| Number of triangles: | 1 | 8 | 35 |
| Number of points: | 3 | 4 | 5 |
| Number of triangles: | 1 | 8 | 35 |
| Number of lines: | 3 | 6 | 10 |
Gargh?!I pondered this for a while as a small child, and then gave up to play outside in the sun. But this scion of the Mystic Rose puzzle had already taken root in my brain, and through the years it has lurked like a perennial weed, occasionally bursting into bloom and crowding out all other thoughts before withering away to lie dormant again. Whenever my mind was idle or underchallenged, it returned to this great unsolved puzzle.
For a long time, I tried to work out a pattern with the small handful of data I had. But try as I might, no patterns emerged. I counted how many times the lines crossed, calling these intersections 'nodes', but found myself no closer to the answer. I grasped at angles, reasoning that if I could group sums of 180 degrees I might be able to count triangles that way. But these angles slipped and spun away from me. I even tried throwing out mathematics as I knew it, embracing networks. But the Mystic Rose puzzle is not a network problem - not only are the lines and points important in themselves, their position in the rose is vital and exact. I bought an A4 gridlined notepad and steadily filled it with arcane diagrams and number patterns. I counted lines, nodes, triangles, roots, squares and angles, I shaded and classed and scribbled and sighed and I was still no closer to the answer. In seven major assaults on the Mystic Rose, each with a different strategy, none worked. For all my efforts, I extracted one tiny piece of information from the rose, and this gave me all the satisfaction of a man who strikes a snake in the grass and finds it is a tiger's tail.
Hidden in the heart of the six-sided rose is a dark secret that was mockingly revealed as I tried to classify the different types of triangles it held, like a cartographer charting undiscovered terrain. In the four- and five-sided roses, the triangles are repeated four and five times. But rotational symmetry has a trick up its sleeve when we get to the six-sided rose, because inside are two equilateral triangles, arranged in a Star of David. When you rotate this shape, the triangles do not repeat. Equilateral triangles are the same no matter which way up you place them, and as a result they do not multiply in the six-sided rose. I'd already suspected that even- and odd-numbered roses might have a different formula. Now it seemed that any rose with a number of sides divisible by three would also be a wildcard. I wasn't even sure whether the three-sided rose should be classed as having one triangle or three. Perhaps there were even different formulas for different shaped triangles!
Exasperated, I wrote to a professor of mathematics seeking help. He never replied. At the time I thought that perhaps he felt he had better things to do than solve witchy puzzles. Today I suspect he never replied because, like me, he couldn't prune the Mystic Rose. Perhaps he's still pulling his hair out now in retirement. Or maybe he's swapped the untameable roses of mathematics for the more easily cultivated flowers of the English garden.
All I know is: to this day, I've kept the Mystic Rose secret, unwilling to unleash it on anyone else the mind-polluting terror of a puzzle so simple yet so complex. But I've been defeated. I cannot solve this puzzle with the mathematics that I have. So I'm offering it to you, world, with all apologies, in the hopes that someone, somewhere, can count the petals of the Mystic Rose.
- Log in to post comments
More like this
I am not a mathematician. I am a programmer. I threw together a quick and ugly Python script to create virtual shapes and count the triangles. It claims to have found 110 triangles for the 6-sided shape, 287 for the 7-sided shape, 632 for the 8-sided shape, and 1302 for the 9-sided shape. I am not entirely sure I trust the results, although I have not found any errors in its findings so far.
Damn you!
You had 20 years. I'll bet you spent time on this one and know why it doesn't work. If I make it to 80 maybe I'll have a different answer.
The upper limit for n points has to be m!/(3!*(m-3)!), where m = n(n-1)/2, based on the hypothesis that each triangle is formed from a crossing of some unique selection of three of the chords. But, some of the intersections will be outside the circle and so should be discarded. Oy.
First, enumerate the kinds of combinations:
1: six points, all permutations of them in pairs.
2: five points. for each point produce a set of six point by duplicating it, then do #1.
3: four, produce all sets of six by duplicating two and again by tripling one, then do #1 to each set.
4: three points, each (unique, unordered) combination contributes precisely one triangle.
So, how to prune?
1: drop combinations for which all three chords share a single point (yes, there's a notional triangle at the intersection, but it has zero size and is congruent with the rim of the circle)
2: drop combinations which have two of the chords parallel (never intersect).
3: drop combinations which have four or more points monotonically ordered (they intersect outside the circle).
4: Drop combinations which include the same sequence pair-wise but with the members of one or more pairs reversed.
And here I'd better stop and pick it up when I get home, assuming I've not been shot down in flames by then. But it does seem to me there is a formula for the counts in each of the prunes.
python rocks. My python fu gets 111 for the 6 sided, but I know that it is counting one particular combination that it should not (in particular, the three line segments that intersect at the center do not make a triangle). Below is my formula for the general case. Note: I'm printing in floating point just to verify that I'm not losing anything due to rounding (which would indicate an error in my formula and/or code). Also, this doesn't subtract for the cases where three lines intersect at a point (makes the off-by-one error in the n=6 case, and will get worse for larger n). If I assume such cases always happen at the center (bad assumption?) then for n odd there is no correction, and for n even just have to subtract n / 2 choose 3. This code also draws the thing, and also highlights the triangles (use up/down arrows).
#!/usr/bin/python
import sys, random
from PyQt4 import QtGui, QtCore
from PyQt4.QtCore import Qt
from math import *
n = int(sys.argv[1])
w = 400
m = 20
xx = [0] * n;
yy = [0] * n;
lx = [0] * n;
ly = [0] * n;
for i in xrange(0, n):
a = i * 2 * pi / n
xx[i] = w/2 + m + w/2 * cos(a)
yy[i] = w/2 + m + w/2 * sin(a)
lx[i] = w/2 + m + (w+m)/2 * cos(a)
ly[i] = w/2 + m + (w+m)/2 * sin(a)
tot = 0
f = ( (n-2.)*(n-3.) / 2. + n - 3. )
tot += n * f
print " n * %f = %f edge triangle (at least one external edge)" % (f, n*f)
f = ( (n-3.)*(n-4.) / 2. - n + 4. )
tot += n / 3. * f
print "n/3 * %f = %f three-point triangles (no vertices internal, three edges internal)" % (f, n/3.*f)
f = ( (n-3.)*(n-4.) / 2. )
tot += 2. * n / 2. * f
print " n * %f = %f two-point triangles (one vertex internal, three edges internal, involving adjacent external edge)" % (f, n*f)
if n >= 4:
f = ( 2. * (n-3.)*(n-4.)*(n-5.)/(3.*2.) )
tot += n / 2. * f
print "n/2 * %f = %f two-point triangles (one vertex internal, three edges internal, not involving adjacent external edge)" % (f, n/2.*f)
if n >= 5:
f = ( (n-1.)*(n-2.)*(n-3.)*(n-4.)/(4.*3.*2) )
tot += n * f
print " n * %f = %f single-point triangles (two vertices internal, three edges internal) " % (f, n*f)
if n >= 6:
f = (n)*(n-1.)*(n-2.)*(n-3.)*(n-4.)*(n-5.)/(6.*5.*4.*3.*2.)
tot += 1. * f
print " 1 * %f = %f internal triangles (three vertices internal, three edges internal)" % (f, 1.*f)
print "rose(%d) = %f" % (n, tot)
hi=0
def intersection(p, q):
p0, p1 = p
q0, q1 = q
if q0 == p0 or q0 == p1:
return xx[q0], yy[q0]
if q1 == p0 or q1 == p1:
return xx[q1], yy[q1]
x1, y1 = xx[p0], yy[p0]
x2, y2 = xx[p1], yy[p1]
x3, y3 = xx[q0], yy[q0]
x4, y4 = xx[q1], yy[q1]
n = (x4 - x3)*(y1 - y3) - (y4 - y3)*(x1 - x3)
d = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1)
u = n * 1. / d
return x1 + u * (x2 - x1), y1 + u * (y2 - y1)
class Colors(QtGui.QWidget):
def __init__(self, parent=None):
global w, m
QtGui.QWidget.__init__(self, parent)
self.setGeometry(50, 50, w+2*m, w+2*m)
self.setWindowTitle('Whatever')
def paintEvent(self, event):
global n, xx, w, m, hi, triangles
paint = QtGui.QPainter()
paint.begin(self)
paint.setFont(QtGui.QFont('Decorative', 10))
paint.drawText(30, 30, "Triangle %d" % hi)
p, q, r = triangles[hi]
#pen = QtGui.QPen(QtCore.Qt.red, 3, QtCore.Qt.SolidLine, QtCore.Qt.RoundCap, QtCore.Qt.RoundJoin);
#paint.setPen(pen)
#p0, p1 = p
#q0, q1 = q
#r0, r1 = r
#paint.drawLine(xx[p0], yy[p0], xx[p1], yy[p1])
#paint.drawLine(xx[q0], yy[q0], xx[q1], yy[q1])
#paint.drawLine(xx[r0], yy[r0], xx[r1], yy[r1])
#paint.drawLine(xx[p0], yy[p0], xx[p1], yy[p1])
paint.setBrush(Qt.red)
x0, y0 = intersection(p, q)
x1, y1 = intersection(p, r)
x2, y2 = intersection(q, r)
paint.drawPolygon(QtCore.QPointF(x0, y0), QtCore.QPointF(x1, y1), QtCore.QPointF(x2, y2))
paint.setPen(Qt.black)
for i in xrange(0, n):
paint.drawText(lx[i]-5, ly[i]+5, str(i))
for j in xrange(i+1, n):
paint.drawLine(xx[i], yy[i], xx[j], yy[j])
paint.end()
def keyPressEvent(self, event):
global hi, triangles
if type(event) == QtGui.QKeyEvent:
if event.key() == QtCore.Qt.Key_Up:
if hi > 0:
hi -= 1
elif event.key() == QtCore.Qt.Key_Down:
if hi < len(triangles) - 1:
hi += 1
p, q, r = triangles[hi]
self.repaint()
event.accept()
else:
event.ignore()
# enumerate line segments
lines=[]
for a in xrange(0, n):
for b in xrange(a+1, n):
lines.append((a, b))
def intersect(p, q):
p0, p1 = p
q0, q1 = q
if q0 == p0 or q0 == p1 or q1 == p0 or q1 == p1:
return True
return (p0 < q0 and q0 < p1) != (p0 < q1 and q1 < p1)
def degenerate(p, q, r):
p0, p1 = p
q0, q1 = q
r0, r1 = r
if p0 == q0 or p0 == q1:
if p0 == r0 or p0 == r1:
return True
elif p1 == q0 or p1 == q1:
if p1 == r0 or p1 == r1:
return True
triangles=[]
c = len(lines)
# pick three distinct line segments
for i in xrange(0, c):
p = lines[i]
for j in xrange(i+1, c):
q = lines[j]
if not intersect(p, q):
continue
for k in xrange(j+1, c):
r = lines[k]
if not intersect(p, r):
continue
if not intersect(q, r):
continue
if degenerate(p, q, r):
continue
triangles.append((p, q, r))
print "enumerated %d triangles" % (len(triangles))
for i in xrange(0, len(triangles)):
print "triangle %d = %s" % (i, str(triangles[i]))
app = QtGui.QApplication(sys.argv)
dt = Colors()
dt.show()
app.exec_()
@kevin
Excellent work, but the assumption that 3 line intersections only occur in the centre is bad. However, it does look like you could predict how many 3 line intersections occur quite easily.
Behold, the online encyclopedia of integer sequences to the rescue: A00600
I should add, for those who don't want to chase down the references from the encyclopedia, that a recurrence for the general case is given here, in a paper by Steven and Tim Sommars. Don't follow the link if you want to work it out yourself.
Darn it, have to remember to check links in preview. Correct link. Scroll down to the bottom to see the recurrence.
Ellindsey @1, I counted 80 triangles for the six-point case, by hand. 13 triangles with 6-fold rotational symmetry, plus the two big equilateral triangles. And since Mr. Swain thinks it's 81 or 82, how sure are you on the 110 count? Have you checked your code against the 3-, 4- and 5-point cases?
Nevermind @6. I fail.
Curses. I thought I was doing so well until I came to working out where the 3-line intersections are. My formula seems to work up to n=6, apart from the spurious 111th triangle.
A problem for another day.
I'd post my code here, but I can't figure out how to keep the comment formatting from mangling the spacing, and python needs spacing to be unmangled for flow control But it seems to work for the smaller cases (3,4,5 sides).
@9: Just post your code to a pastebin, then put the URL to said paste here. :)
Maybe this is off base, but I get 200 even when counting every triplet combination of "nodes" where each of the three nodes is connected by a line to the other two.
nevermind. made a stupid assumption. reformulating.
173, not counting cases where all three lie on the same line, maybe?
As a kid, I believed that a triangle could also consist of three lines, angles of 180, 0 and 0 degrees. That would explain some of the seemingly inflated counts in the code.
Nevermind. Found the rest of the cases of my stupid assumption, and arrived at 110 by another method.
A couple of my comments are stuck in moderation, but I'll point out that 110 is the correct number for 6, and you can see more terms in the sequence at the online encyclopedia of integer sequences.
Huge spoiler: OEIS, sequence A006600.
Oh, wait, somebody beat me to it. Damn.
There are some very desirable properties with n prime. For instance, any intersection (other than the nodes on the circle, of course) will never be the intersection of more than two lines, and in turn that can make the counting much easier. I would be surprised if simple observations with n prime doesn't lead to a better understanding of how the compound numbers work here. (I bet the Burnside Lemma would come into play when going from understanding the primes to the compound numbers, at least thinking from group theoretical perspective)
My program gives me this series: 1, 8, 35, 94, 287, 438, 24519, ... :(
I guess there gotta be a bug somewhere.
You're all taking up the challenge with such passion, I can't tell you how happy that makes me.
I thought I was doing so well until I came to working out where the 3-line intersections are. My formula seems to work up to n=6, apart from the spurious 111th triangle.
@12
Ok, I've put my code at the following paste dump:
http://p.opsat.net/v/1ui
I make no claims for this code being efficient or optimized, and it doesn't give any kind of graphical output or anything beyond a number of how many triangles it found, but it does seem to get the right answer.
Like red pepper, I have a formula (valid for n>5) that works except that it counts the cases where three lines intersect at a point. For n=6,7,8,9 it gives
111, 287, 644, 1302
which is correct for n-7,9 but gets it wrong for n=6,8 (conjecture: the formula is correct for prime n, but overcounts for compound n?)
The formula is
Number of triangles = (n,6) + 5 * (n,5) + 4 * (n,4) + (n,3)
where (n,k) is the binomial coefficient "n choose k". This comes from Gray Gaffer's chord counting idea (see second comment.)
It seems that it's going to be tricky to correct for the multiple intersections - as Frank points out, they don't only occur at the center. The intersections at the centre can be accounted for by subtracting (n,3) whenever n is even, which you can deal with by adding the extra term
- (1 - (-1)^n) * (n,3)
I like that, because it doesn't involve defining any extra functions (you know... "let a(n) be 1 when n is prime and zero otherwise...") but I suspect you'll have to define a bunch of stuff like that to get the full formula.
Addendum: the last formula there should read
- 1/2 * (1 + (-1)^n) * (n/2,3)
Cloudoid has successfully counted the petals of the 6- and 7-sided Mystic Roses with a clever technique and a little maths: see the solution
# CGI / Perl Programming Intro #
Command gatway Interface (CGI)
Pratical Extract & report language (PERL)
1. What are the limitations of using HTML on the World Wide Web?
HTML is static, which means that the information on a web page does not change unless the web designer manually updates it. HTML data is preset, which means that the web designer decides what and when a user will see on a web page.
2. What is the purpose of CGI?
CGI or Common Gateway Interface is a protocol that defines the way web servers should handle information and communicate with any number of other programs.
Web Server
web server is any computer program that uses the HyperText Transfer Protocol (HTTP) to provide information to web browsers using the Internet. HTTP is the protocol that web servers and web browsers use to communicate with one another.
Most command webserver software
Apache
Microsoft Internet Information Server (MIIS)
weee....ang hirap nman..:))))))
So has this been solved yet? Has someone published a solution? I can never manage to get these right by counting alone.
thank you elemanlar idare eder.