Counting Lines

My lunchtime math problem solving group was going through some old American Mathematics Competition problems, and we came across one that asked, in slightly more complicated language, "How many lines can be drawn that intersect at least two points in a 3x3 rectangular array?".

Most of the kids who understood the wording got the answer, and when I asked them how, they said they counted... they drew the dots, drew the lines, and counted them...

So I asked, how would you do it if they had a ten-by-ten array?

Counting the number of lines in an nxn array that contain the maximum number of points, n, is pretty straightforward. There are n horizontal lines that contain n points, and another n vertical lines, and two diagonals. For nxn there are 2n+2 lines that contain n points. In the 3x3 case, there are 2(3)+2 = 8 lines that contain exactly three points. So how to count the 2x2.

After a while I decided that there would be a maximum of n choose 2 lines if no two were collinear, so at most, a set of nine points could contain 9 choose 2 = 36 lines. Now each of the lines that had three points, would use up three different lines from this 36.. think of a line with points A, B, and C all collinear. Instead of three lines, they fall on one, so each line of three points would reduce the possible total of 36 by two... and since there are 8 of these lines, we need to eliminate 8x2=16 lines from the 36 to get a total of 20, 8 with three points, 12 more with only two points.

This verified the students solution by counting, but didn't bring us much closer to the general ten x ten case. For instance in a 4x4 there are some lines with four points (10 of them) and some more with three points (a quick look assured me there would be four) and the rest with only two points. By Starting with 16 choose 2 and eliminating duplication as before, I figured out that there would be 48 of the lines with two points.

By the next time we meet, Conner S. had counted up the number of lines with exactly two points by hand up to n=5 (and had a small error in the n=5 case finding only 100 when there are 108... Examining the case for n=5 is influential, but still, we don't get a really good clue of a general pattern. The sequence for the number of total lines from n=2 to n=5 is 6, 20, 62, 140... you might want to try to find the next one.. I couldn't, and the pattern of lines with exactly two points was equally wild... 6, 12, 48, 108??? (For my students, I will show how the counting technique used above to the possible lines given by n choose 2 to find the number of lines with two points. In most cases (such as the five by five) it is not too hard to count the number of lines that contain three, four, or five points.)

I guess I can be ok with my kids not being able to find the pattern, as it seems that the pattern didn't have any simple solution at all, and was eventually extended, it seems, beyond the hand countable cases by computer search. Afterward they did find a summation notation that is way complicated. I finally searched the On-line integer data base and found the actual numbers... don't look if you are still figuring out the pattern for yourself. This triangular array gives the number of lines containing exactly k points in an nxn array.. At the top of the triangle is n=2, k=2, and as you go down each row the n goes up one... so the numbers in the fourth row(for n=5, a 5x5 array), {108, 16, 4, 12} is the number of lines containing 2, 3, 4, and 5 points.




Interesting to look down the center at the sequence of 4's, as long as the number of points in the line is more than (n+1)/2 and less than n, there will be four such lines. Predicting the rest of the table as yet is beyond me.. if you see a simple way to calculate these values, do please advise.

Art Benjamin for Math Czar

A Cool Tool, Derivatives Without Calculus

After the AP Calculus exam is over and there are still a few weeks of school left, I like to show my students some interesting things that are related to calculus ideas, but have no actual calculus in them. One of those ideas is finding derivatives of polynomials using synthetic division, and another is the idea of how the Polar of a point gives the tangent line to a point on a quadratic curve without calculus.

A brief explanation for those who are not aware of this method. a standard type of problem in calculus is to take a conic, such as an ellipse, and use implicit differentiation to find the tangent line to a point on the curve. For example we might take and find the tangent at some point such as (3/sqrt(10),6/sqrt(10)). It is a nice example because most capable students can solve it for y and do the derivative of the positive half of the ellipse and find the derivative, but it is gets a little messy. Then they can do it by the implicit method and see that (assuming all was done correctly) they get the same result.. the calculus they are learning seems to agree with the stuff they already feel they know.

Now for the Polar method. It seems that if you take the equation, and replace one of the two variables in each square with the value of the point, you get the value of the tangent. For example, the tangent to is found by writing the equation . The image at top shows the ellipse and its tangent.

It seems a little harder to do with a parabola because one of the terms is not a square, but you can replace the y with (y+c)/2 (where c is the y-value at the point of tangency we seek. For example the tangent to the curve y=x² at the point (2,4) is given by (y+4)/2 = 2x. When simplified to y=4x-4, most semi-capable calculus students will recognize that it is correct.

I was recently wondering about this idea. I had always thought it only applied to quadratics, and had never seen it applied beyond that level. I began to wonder what would happen if you applied it to a cubic, so I picked an easy one, y=x³ at the point (1,1)to see what would happen. Replacing y with (y+1)/2 and one x with 1, and another with (x+1)/2 we get (y+1)/2= (1)(x)(1+x)/2, which simplifies to y=x² + x -1 . The two graphs are shown below.


Ok, its tangent, but not a linear tangent... that was revealing in itself.. then it hit me that the tangent to y=x² + x -1 at (1,1) has a slope of three, so if I applied the polar approach one more time, I would get the familiar tangent line we found in calculus...

I don't yet understand how these descending degree equations tangent to the same point are related, and plan to play with them some more... if you understand a little more than I what is happening here, and how it relates to the traditional calculus, a tutorial would be appreciated. I did follow up and check it out with x³ + 3xy + y² = 4 and the same process works for a mixed implicit function (at least it did with this one).

Enough for now, but more ahead.

The Lucasian Chair, From the FFT of Calculus, to String Theory

This month the Lucasian Chair of mathematics at Cambridge, just down the road from my school here in Lakenheath, was passed to Michael Green, a physicist and pioneer in String Theory. Officially, I believe, he will replace the retiring Stephen Hawking on November first.

The Lucasian Chair began with a grant of land (and a huge library of books)from the Member of Parliament to the university, Henry Lucas, to provide a 100 pounds sterling annual stipend. The first chair was Issac Barrow, a classical mathematician. It may be surprising to young people who are taught that Newton invented the Calculus, that Barrow, Newton's teacher, gave the first general proof of the First Fundamental Theorem of Calculus, the one that links integration and differentiation together.
Amazingly, after only five years, he gave up the chair to his student, Newton. Newton is probably one of the two most famous holders of the chair, the next most well known being the retiring emeritus chair, Stephen Hawking.

After Newton, the chair passed through a succession of mathematicians that would not be recognizable to the common lay person. In fact, his successor, William Whiston, would probably not be a name recognized by most mathematicians. Born in 1667, the year after the great fire of London, he was headed for the top, and rubbing elbows with the best for a while. He served as Newton’s deputy at Cambridge, where he was a fellow. He was one of the earliest proponents of the theory that comets had a periodic behavior, along with Halley. He was a classical scholar and mathematician who, if remembered at all, is remembered for his contributions to recreational mathematics. His translation of the works of Flavius Josephus may have contained a version of the famous Josephus Problem, and in 1702 Whiston's Euclid discusses the classic problem of the Rope Round the Earth, (if one foot of additional length is added, how high will the rope be). I am not sure of the dimensions in Whiston's problem, and would welcome input, I have searched the book and can not find the problem in it, but David Singmaster has said it is there, and he is not a easy source to reject. It is said that Ludwig Wittgenstein was fascinated by the problem and used to pose it to students regularly.
Whiston was expelled from his chair on 30 October 1710; at the appeal of the heads of colleges. Comets were also part of this disaster in his life. He had become famous for his studies that stated that the Biblical flood had been caused by a comet, and gave support for other geological impacts of comets on the Earth. Whiston was removed from his position at Cambridge, and denied membership in the Royal Society for his “heretical” views. He took the “wrong” side in the battle between Arianism and the Trinitarian view, but his brilliance still made the public attend to his proclamations. When he predicted the end of the world by a collision with a comet in October 16th of 1736 the Archbishop of Canterbury had to issue a denial to calm the panic.

After two holders who seemed to be little more than groveling toadies, (Saunderson and Colsen) the chair passed to Edward Waring in 1760. In number theory, Waring's problem, proposed in 1770, asks whether for every k there exists a positive integer n such that every natural number is the sum of at most n kth powers of natural numbers (for example, every number is the sum of at most 4 squares), . The problem and its affirmative solution is now called the Hilbert–Waring theorem, proven by Hilbert in 1909.

I will continue this study anon...