Draw a circle, put a few points on it, connect them all, and count how many regions. If you have no points you get no lines, which gives 1 region - the whole interior of the circle. One point still gets you no lines and one region. Two points gives one lines and splits the interior of the circle into 2 regions. What happens for 3, 4, or 5 points?
It looks like a very familiar pattern, doesn't it?* Now check to see if the pattern holds for 6 points. Hmm...
The goal with this problem is to find an expression (formula) for the number of regions when there are n points. After many years of playing with this problem on and off, I came up with a formula, but I didn't understand why it worked, and so I couldn't be sure if it would always work. I was running an online study group of people working through Harold Jacobs book, Mathematics: A Human Endeavor. This problem appears in the book, and I wanted to be able to lead any discussion that might come up about it. So I needed to understand why my formula worked. I turned to Google, and found lots of answers. They made sense, and I thought I understood.
But my understanding was shallow, and my memory is terrible, so I forgot. That was perfect. I knew I was capable of understanding it, and the next time around, I refused to look it up. With lots of work and my fair share of false starts, I finally figured it out. At first I felt bad about my solution method - I felt like I'd hit the problem with a big hammer, instead of delicately teasing it apart. I'm proud of it now, and I've written a paper describing my solution. I won't post it here, because I think this problem is so worth playing with, I don't want to make finding a solution online any easier than it is. But you're welcome to email me to request it.
I started writing this post over a year ago, and abandoned it, because I couldn't figure out how to say enough to pull people in, without giving too much away. James Tanton has just posted a video that offers a new twist on this problem, which got me thinking about it again, and I'll leave you with that.
_____
* This picture comes from James' video.
Posts
I love this post, Sue! I just linked it on my facebook, where I am posting something cool about powers of two, powers of ten, or 42 every day this month.
ReplyDeleteThis was perfect for today!
And my word verification challenge on your blog is "taxess" which is an elision of my daughters' nickname for me ("tax goddess")
How cool is that!
Incredibly, Dave Richeson wrote an entire book about this problem, ...
ReplyDeletehttp://pballew.blogspot.com/2009/04/eulers-theorem-of-planer-graphs.html
I've read that book, and enjoyed the parts I understood. I would not have thought of it as being related to this problem. I'm obviously not seeing the big picture here. I like your post.
ReplyDeleteI will think about this more after I take a nap. ;^)
Mary, how'd 42 get into the mix?
ReplyDeleteThis problem was offered to me as an example of a pattern that breaks. I recall playing some more, a few of us, and one of our number discovering something neat:
ReplyDelete1
1+1
1+2+1
1+3+3+1
1+4+6+4+1
5+10+10+5+1
15+20+15+6+1
35+35+21+7+1
...
1. Do I remember correctly?
2. Is there a nice link to what is physically going on? (either in the Richeson book or the video)
3. Is this easier to understand as:
(k=0 to 4) Sum C(n,k)
or as:
2^n - (k = 0 to n - 3) Sum C(n,k)
(Look at the regions? Look at the regions that fail to be formed?)
Interesting. I haven't thought about this in a long time.
Jonathan
Jonathan, I feel too stressed for time to play right now. (Shame, isn't it?) But this looks fascinating. It seems that you're saying that you can use Pascal's triangle to predict the proper number of regions if you start leaving off numbers at the 5th row.
ReplyDeleteI'll look forward to exploring this when I'm on vacation or something.