Update!
Answers to General Formulas for |x| + |y| = N:
ON: 4N
INSIDE or ON: N2 + (N+1)2 = 2N(N+1) + 1 = 1+4+8+...+4N
OUTSIDE the 'diamond' but INSIDE or ON surrounding square:
2N(N+1) = 4+8+...+4N
TOTAL: (2N+1)2
[Pls indicate any discrepancies you find!]
The following starts with a fairly simple pattern but watch out -- students from Middle School through Algebra 2 and beyond can take this as far as their imagination and skill can carry them. The questions below review absolute values, inequalities, graphs, geometry, etc., but that is the tip of the iceberg. Prealgebra students should start with simpler values to get the idea. Have them make a table of their findings as suggested at the bottom.
One could begin with a variation on an SAT-I, SAT-II type or math contest question:
How many ordered pairs (x,y), where x and y are both integers,
satisfy |x| +|y| ≤ 6?
Note: If this were to appear on the 'new' SAT, the inequality would be replaced by an equality. or the '6' would be replaced by a smaller number.
Here's a restatement using the terminology of lattice points:
In the coordinate plane, a point P(x,y) is said to be lattice point if both coordinates are integers.
How many lattice points are inside or on the graph of |x| + |y| = 6?
Answer: 85
Sorry for giving it away, but the objective is to discover ways to derive this result, not the result itself.
When I see questions like this, my inclination (as a mathematician) is to generalize, that is, try to understand a general relationship if the '6' were replaced by N.
Here is the more advanced generalization (one could go further!):
We are investigating the number of lattice points inside or on the graph, G, of
|x| + |y| = N, where N is a positive integer. We will also consider the smallest square, S, whose sides are parallel to the coordinate axes in which the graph of
|x| + |y| = N is inscribed. [This really needs to be drawn but I'll leave it to the reader's imagination. The top side of this square is part of the line y = N.]
(a) Derive a formula for the number of lattice points inside or on G.
(b) Derive a formula for the number of lattice points inside or on S
(c) Derive a formula for the number of lattice points outside G but inside or on S.
Notes, Comments:
For the younger students, or for any group that isn't quite ready for the above, I strongly recommend building the pattern one step at a time and to record their results in a table:
|x| + |y| = 0 (o is not a positive integer but it makes sense to start here) to |x| + |y| = 1 to
|x| + |y| = 2,...
Also, there are alternate formulations (or a variety of patterns) for the general number of lattice points. Don't be surprised if your students find them! Of course, they should be encouraged to show they are all equivalent. Questions about the geometry of the figures could also be raised (if time permits). For example, some students do not fully appreciate that the diamond-shaped graph of |x| +|y| = N is in fact a square, Now, what would its area and perimeter be...
This investigation can be started in class then assigned to be finished outside of class, preferably with a partner. I plan on starting this with my 9th graders on Mon or Tue but I will need to review absolute values, graphs, etc., and I will develop it incrementally. I will be more than happy if, in one 40 minute period, they can complete a table showing the correct number of lattice points for N = 0,1,2,3!
[Additional but critical point: I am not suggesting that these kinds of extensive explorations should ever replace the need to deliver content and develop skills. These are intended to be enrichment activities, no more, no less!]
Sunday, March 25, 2007
In-Depth Investigation of Patterns: Lattice Points, Algebra,...
Subscribe to:
Post Comments (Atom)
Posts
8 comments:
You don't want them to count horizontally or vertically? There is a neat x^2 + (2x + 1) +x^2 that drops straight out.
jonathan--
I would expect them to add one of those 2 ways. Actually, the original SAT problem I saw asked only for the points on the boundary which students have a better chance of formulating in general since it's just '4N'.
For whatever reason, I added horizontally, but, from symmetry, it doesn't matter. Personally, I was more interested in the relationship between the points inside and those outside. For N = 6, the outer square has 13^2 = 169 points. This leads to 85 points inside or on the 'diamond' and 84 points outside. This could be explained visually by noting there are 6+5+4+3+2+1 = 21 'outside' points in each quadrant. Thus the number of 'outside' points is 4 times T_6 where I'm using the notation to stand for the triangular number of rank 6. Triangular numbers seem to play a huge role in many of these geometric combinatorial problems.
These beautiful connections are so important for the mathematical development of our students, IMO.
When all this is done, you can talk about the number of lattice points contained within the closed disk of radius r. This is Gauß' circle problem. MathWorld has an entertaining discussion; you can use it as a starting point for estimation, the O-notation, and probably a few more things. Of course, this isn't something 9th graders could do too much work on.
great ideas, eric!
I was thinking of going to the disk next. I do think the 9th graders can graph most of the solutions for the interior and on the disk but would need more machinery to verify their conjectures (Pythagorean, distance formula, etc). I will work on it. Now as a real challenge, how about solving the problem in n-dimensional space!
Here's a different insight into the lattice point problem. I will post the general formulas later on.
The area of the square formed by |x| + |y| = 6 is easily shown to be 72. Pick's Theorem relates the area bounded by this square with the number of lattice points on the boundary, B, and the number of lattice points in the interior, I, as follows:
Area = I + B/2 - 1.
It is easy to show that B = 24 for this graph, so 72 = I + 24/2 - 1 which leads to I = 61. Adding we obtain that the total number of lattice points is 61+24 = 85. Pick's Theorem is beautiful although not easy to prove. Worth showing this to middle school students though (particularly if they have experimented with geoboards).
If you do a change of basis, you count diagonally; you get two sets of grids and quickly see that the answer is (N+1)^2 + N^2.
I tricked myself this way though, since I overlooked the offsetting grid of 6x6 inside the 7x7; my first thought was 49. I had to graph it all to see...
Going to a circle would be obnoxious. I say this mostly for reasons of "squaring the circle" - the answer ends up being scale dependent, as certain points just make it in, or not.
To increase the difficulty somewhat, but not the inherent difficulty, perhaps going to:
|2x| + |y| <= 8.
Using the graphical approach and diagonal counting, this yields 5^2 + 3*4^2.
The next step is:
|2x| + |y| <= 9.
Here, max(x) is still 4, which complicates things a little. Still, the diagonal approach gives 3*5^2 + 4^2 = 91.
This suggests that the form of the general solution will be:
Points = a*(N+1)^2 + b*N^2
, where N = Min(max(x), max(y)). In other words, a linear combination of "big" (N+1) and "small" (N) diagonal squares.
Now that we have the general solution, all we need is the general problem:
|Ax| + |By| <= C.
For convenience, take A>B.
Then, N= Int(C/A)= max(x)
and M= Int(C/B) = max(y).
Now, the range, R, of y is (-M,+M) for a total (lattice points on y axis) of
R= 2*M +1
A hasty conjecture is that a,b satisfy:
R = a*(N+1) + b*N
Can we prove this? If the "big"
diagonal square is counted "a" times, then the diagonals of each will cross the y-axis (N+1) times. The remainder of the y-axis values must be associated with the "small" diagonal squares. So, yes, we can prove this and a,b must satisfy the equation.
At this point, if we have a, we have b. The value of a can be found by examining the range of y at x = N. Denoting this lower case r, and the maximum of y at x=N as lower case m, we see:
m = C - A*N
and
r = 2m + 1
However, r is simply how many times the maximum value of x is repeated, and thus, how many times the "big" diagonal square is repeated. In other words, this is "a" that we are looking for:
a = 2m + 1
To summarize:
For:
|Ax| + |By| <= C
x,y,A,B,C integers, A>B>0,
(A+B)<=C
has lattice points that number
P = a(N+1)^2 + bN^2
where
N= Int(C/A)
M= Int(C/B)
m = C - A*N
R = 2M + 1
a = 2m + 1
b = (R - a(N+1))/N
I think this works. FYI, this solution is influenced by years of solving various practical problems with spreadsheets.
tim--
thank you for your awesome insight and extensions!Practical problems with spreadsheets? I suspect you have a passion for math that goes beyond the practical! I will consider developing some examples around your results if that's ok with you.
I considered generalizing like you did but eric jablow got me 'going in circles!'
The circle problem is really a magnificent piece of math analyzed fairly extensively by Gauss. I decided to bring Pick's Thm into it because it just doesn't get the attention in schools that it so richly deserves...
1111111111111111
Post a Comment