Recreational Math Challenge

[Darwin]

Some emails from a friend reminded me of this odd little math problem. I'd be interested in seeing if other folks can come up with the solution.

I never quite got into higher math, but I do enjoy the lower variety. In high school I did well enough through algebra and geometry--both plane and solid--but flunked trig. I tend to blame it mostly on the teacher, who didn't seem to be able to transfer his understanding from his own brain into mine (a problem shared by all of my college programming instructors). Even my brother-in-law, who had gone through college trig couldn't figure out a lot of my homework problems.

When I was stationed on Taiwan (1964-66), Shulinkou Air Station had personnel from all services: Air Force, Army, Marines, and Navy. All Operations personnel worked rotating shifts: days, swings, and mids. One night after coming off of the swing shift, several Army friends and I were sitting in the snack bar when a Swabbie came in with an odd question. He was taking some kind of math course and needed some help with a problem. We spent some time on it, drawing on paper napkins, but none of us could figure it out. I never found out whether or not he came up with an answer, but the problem stuck in the back of my mind and nagged at me for years.

Near the end of my first tour in Japan (about 1972), I did something foolish that resulted in the cartilage on the backs of my kneecaps developing some cracks. As a result, I couldn't climb the stairs to my third-floor office, and ended up all by myself at a desk in a map storage room on the first floor. I had some translation work to do, but things tended to get boring with no one to talk to, so I sometimes took a break and amused myself with attempts to trisect an angle using only a compass ( famous impossible problem), and with that ancient math problem. For the most part, I just doodled around with it, having no idea of how it could be approached.

Finally the day came when I really got into it. I didn't know anything about programming at that time, but I finally realized that I needed to come up with an algorithm to solve it. Once I had that figured out, the answer came about pretty quickly. A big part of the solution involved a procedure that I had actually discovered during the Southwestern University entrance exam. In the process of applying this procedure, I also came up with a matrix of numbers that turned out to have been previously described by a famous mathematician for whom a once-popular programming language was named. (Surely that's enough of a clue for the math nuts here.)

Here's the problem:

1. Imagine a circle with 360 evenly spaced points around the perimeter.

2. A line is drawn from each point to each of the other 359 points.

3. Figure out how many two-line intersections there are within the circle. (A two-line intersection is produced each time one line crosses another line, regardless of how many other lines may cross at that point. Therefore, a node where three lines intersect consists of three two-line intersections, a node where four lines intersect consists of six two-line intersections, and so on.)

4. Figure out how many two-line intersections there are including the intersections at each point on the perimeter. This is easy once you've figured out the previous problem.

Can you see the approach to take? (It definitely doesn't involve drawing all those lines and counting the intersections, as the answer to each part of the problem is well over half a billion.) I came up with a reasonably compact formula for calculating the number of intersections for any number of points for each part of the problem.

It probably won't take anyone else six or seven years, as it did me. If you think you've got an answer, but don't want to spoil it for others, you can pm me.

[jsluder]

Can you see the approach to take? (It definitely doesn't involve drawing all those lines and counting the intersections, as the answer to each part of the problem is well over half a billion.)

But drawing it might actually be fun. Counting the number of intersections, or figuring out a formula to compute it, sounds more like work.

[MarkB]

Recreational Math isn't that an oxymoron?

MarkB

[emmline]

I have about a 1% success rate for thinking of answers to things like that in right-brained flashes. I expect this one to fall squarely in the remaining 99%.
If I were stuck in a map-room with bad knees I'd probably work on this kind of stuff too.

[cowtime]

Recreational Math isn't that an oxymoron?

MarkB

Most definately :roll:

[Cynth]

You use words that really scare me like algorithm and matrix. Geez, you amuse yourself by trying to trisect an angle and you actually know that it is a famous impossible problem? You are my idea of higher math. I got too anxious to actually read what you are asking about. Good luck to all of you.

[Cynth]

You don't need to worry about me spoiling it for others.

[Flyingcursor]

A lot?

[EricWingler]

Each set of four points taken from the collection of 360 will determine a unique intersection point. So the number of two line intersection points inside the circle is the number of combinations of 360 things taken four at a time, that is, 360*359*358*357/(4*3*2*1) = 688,235,310.

Many people assume that "impossible" means that no one has been able to do it, so they devote a great amount of time trying to achieve fame and fortune by attempting to do an "impossible" task. However, in mathematics "impossible" means that it has been proven impossible. All attempts to trisect an angle with compass and unmarked straightedge will fail because this has been proven to be impossible. However, there is a way to trisect an angle with a compass and a marked straightedge.

[Cynth]

Okay, here is a math problem I have trouble with:

I was born Nov. 1, 1949

Today is March 24, 2005

How old am I? I mean I have a rough idea, but I'm always off by a year or so. I see that subtracting 1949 from 2005 gives 56---is that what I will turn this year or is that what I am now? Is there a way to remember how to figure this out?

[ChrisA]

Each set of four points taken from the collection of 360 will determine a unique intersection point. So the number of two line intersection points inside the circle is the number of combinations of 360 things taken four at a time, that is, 360*359*358*357/(4*3*2*1) = 688,235,310.

Well, that solves the hard part!
However, if I understand the problem correctly, it's a bit more... you only counted
interior intersections. Each perimiter point has 359 line segments meeting at their endpoints.

I think a 359 line intersection counts as (359 * 358) / 2 two line intersections.
So add another 360 * 64,261 = 23,130,360...
688,235,310 + 23,130,360 = 711,365,670

That's a clever solution though, I was looking for a sigma-sum that described the number
of intersections of rays from two points. I didn't quite have it, though. That would also
have involved adding in the perimiter points after calculating the interior points.

Oh, and the trisection problem was only proved impossible a few years ago, so when
people say they used to try to solve it (I used to play with it to), they generally mean
-before- it was proved impossible. It's now been solved, in a sense, by proving it impossible.
(In the sense that it's a problem with an answer of 'you can't' instead of a problem
without an answer.)

The proof was generated by a computer algorithm, and was either -the- first, or one of
the first, mathematical proofs to be calculated by computer. It made it controversial at
the time, and lots of people spent a lot of time pouring over the steps of the proof
trying to show that it was flawed. But it wasn't, and the controversy evaporated and
now it's a perfectly acceptable technique (and has solved some more problems).

[Darwin]

Each set of four points taken from the collection of 360 will determine a unique intersection point. So the number of two line intersection points inside the circle is the number of combinations of 360 things taken four at a time, that is, 360*359*358*357/(4*3*2*1) = 688,235,310.

Cool! I was sure that on a board this size we'd have some real mathematicians around. (Aboard?)

This shows the difference in the way someone who knows what they are doing will solve such a problem (and which was probably the approach being taught in that sailor's math class), and the way someone who knows nothing will approach it. My solution was more what I'd call "algorithmic" (sorry Cynth), than mathematical.

Here's how I figured it out. It's a bit long and tedious, so if you're sleepy, be sure to sit in a way that you won't bump your head if you nod off.

The way I started off was by actually counting the number of intersections for several of the smallest numbers of points. The fewest number of points that will produce an intersection is 4. Here are some of the numbers (points followed by intersections):

4 : 1
5 : 5
6 : 15
7 : 35
8 : 70
9 : 126

Then I lined up the number of intersections like this:

1 5 15 35 70 126

Next, I asked what the next number in this sequence should be. In the entrance exam I mentioned, there were quite a few questions of this type, with a variety of sequences. It just happened that all of them yielded to the same approach. I discovered that basic approach in the middle of the exam--it's not something I learned in school. That approach was to subtract each number from the following number. I ended up adding a zero at the beginning of the series, so it starts off like this:

    0     1     5     15      35       70       126
0      1     4    10      20      35       56

That wasn't too revealing, so I did the same thing with the second line and kept on until something obvious appeared:

             0     1     5      15       35       70       126
         0      1     4     10       20       35       56
      0     1      3     6      10       15       21
   0    1      2      3      4        5         6
0    1      1     1      1       1         1

Now it becomes obvious that the next number in the series can be found by adding 1 to the last number in the second line (1 + 6 = 7), adding that to 21 to get 28, adding that to 56 to get 84, and adding that to 126 to get 210. Sure enough Eric's formula gives us 10 * 9 * 8 * 7 / (4 * 3 * 2 * 1) = 5040 / 24 = 210.

Of course, I didn't want to sit and fill in these values all the way up to n = 360, so I started looking for a way to get from one line to the next for any value of n. After a lot of fiddling around, and lots of wasted paper, I realized that to get from the second line from the bottom to the next line up, you can multiply the number by the next number in that sequence, then divide the result by 2, thus n2 = n1 * (n1 + 1) / 2. The rest of the operation is similar.

To get from line 3 to line 4, you add two to n1 and divide that by 3, then multiply that by n2, thus n3 = n2 * (n1 + 2) / 3.

To get from line 4 to line 5, you add three to n1 and divide that by 4, then multiply that by n3, thus n4 = n3 * (n1 + 3) / 4.

Finally, we want to get rid of all variables except for n1:

n4 = n3 * (n1 + 3) / 4
n4 = n2 * (n1 + 2) / 3 * (n1 + 3) / 4
n4 = n1 * (n1 + 1) / 2 * (n1 + 2) / 3 * (n1 + 3) / 4

Arranging the order of elements into a more orderly looking sequence, we get:

n4 = n1 * (n1 + 1) * (n1 + 2) * (n1 + 3) / (2 * 3 * 4)

Since n1 is actually the three less than the number of points (np = n1 - 1), this becomes:

n4 = (np - 3) * (np - 2) * (np - 1) * np / 24

This is obviously quite different from knowing the principle that Eric quoted. In a way, it's a wonder that I got the solution at all. On the other hand, this is the kind of thinking that I use all the time to solve real-world programming problems.

The solution to the second part of the problem can be approached in a similar manner. The number of two-line intersections for any number of lines (ln) turns up as n2, but with n1 being np - 1 to start, and you multiply that by the number of points on the circle, above, thus (as ChrisA showed):

ln = np * (np - 1) * (np - 2) / 2

Some time later, I was browsing a math book in the library and found something that I recognized from my solution to part 1 of this problem. If you rotate my matrix (sorry again, Cynth) clockwise by 135 degrees, dump the line with zeroes, and then fill it out to make a symettrical triangle, the leftmost portion goes from this:

             1     5      15       35       70       126
         1     4     10       20       35       56
      1      3     6      10       15       21
   1      2      3      4        5         6
1      1     1      1       1         1

to this:

                                       1
                                  1         1
                             1        2         1
                        1       3          3        1
                    1       4        6          4       1
               1       5       10      10         5       1
          1        6       15      20       15      6       1
     1        7       21      35      35        21      7      1

and so on.

When I saw this figure in that math book, it was labled Pascal's Triangle. I recognized that it was the same set of numbers that I had found in solving the sailor's problem and, since I had discovered it entirely on my own, I decided to take the liberty of naming my version of the matrix Wright's Parallelogram.

Hope some of my fellow non-mathematicians had some fun with it. I did get a couple of PMs on the subject.

[emmline]

Okay, here is a math problem I have trouble with:

I was born Nov. 1, 1949

Today is March 24, 2005

How old am I? I mean I have a rough idea, but I'm always off by a year or so. I see that subtracting 1949 from 2005 gives 56---is that what I will turn this year or is that what I am now? Is there a way to remember how to figure this out?

You're 55 until Nov. 1. Unless you want to be 29. Or unless you're one of those people who likes the years, in which case you can start calling yourself 56 right away, even though you're technically not.

[Tyghress]

I've been fascinated with mathematical recreation since I discovered Martin Gardner's wonderful columns in Scientific American, and then Doug Hoffstaeder's (I can't spell his last name correctly!) when Gardner retired. As a pleasant pasttime I still delve into the four 4's and try to work out a dozen or so numbers...good way to occupy a snowy afternoon!

I haven't tried this one yet, but will do so this weekend...thanks for the puzzle!

[Cynth]

You're 55 until Nov. 1. Unless you want to be 29. Or unless you're one of those people who likes the years, in which case you can start calling yourself 56 right away, even though you're technically not.

Thank you for addressing such a low level problem! Um....I think I'll stick with 55 until November. 29 would not be too convincing I'm afraid, nor would 39 unfortunately.

So I do the subtraction and that is how old I will be on my birthday in that year. Okay, I will memorize this.