Lattice Points in a RectangleDate: 06/04/99 at 10:56:54 From: John Subject: Regarding areas Prove that in any rectangle centered at (0,0) with an area greater than 4, you can find lattice points other than (0,0). I was given a theorem relating to pigeonhole principle that states "given areas A1, A2, ..., An and an area A, if A1+A2+...+An > A, then there is overlap." My conjecture is that any rectangle centered at (0,0) with an area of 4 contains lattice points and so any area greater than 4 must also contain lattice points. However, I cannot prove the first part and I am not even sure that this is sufficient proof. I've also given the vertices points (x1,y1), ..., (x4,y4) and expressed the area as a product of distances, realizing that for every vertex x1^2 + y1^2 = ... = x4^2 +x4^2 since the distance from each vertex to the center must be constant. My last thought in this route was that each X and Y coordinate must be at least some number 'n' in order to contain a lattice point but I cannot find n. I believe this proof must be much simpler than I am making it but I've thought about it for about 3 days now and tried these two routes. I would greatly appreciate help. Thank you. Date: 06/07/99 at 19:38:03 From: Doctor Wilkinson Subject: Re: Regarding areas Hi, John! This is a special case of what is known as Minkowski's Theorem, and it is kind of tricky, so you shouldn't feel too bad if you've had trouble with it. It's one of those things that seem easy once you see them, but it's hard to find the right way of looking at it. If P = (x,y) and m is any real number, we denote the point (mx,my) by mP. In particular we denote (-x,-y) by -P. If P = (a,b) and Q = (c,d), we denote (a+c,b+d) by P+Q and (a-c,b-d) by P-Q. That is, we do addition and subtraction and multiplication by scalars component-wise. Let's call the rectangle S. The two facts we need about our rectangle S are (a) If P is in S, so is -P; and (b) If P and Q are in S, so is (P+Q)/2. Everything else is just a distraction. In particular, your second route is not the way to go. So let S be a set of points with properties (a) and (b), and with area greater than 4. Look at the set S/2 that you get by shrinking S by a factor of 2; that is, it is the set of points P/2, where P is in S. Its area is 1/4 the area of S, so it's greater than 1. Now think of S/2 as being marked out with ink on the coordinate plane, viewed as an infinite piece of transparent quad-ruled plastic. Cut the paper into squares along the grid lines, and pile all the squares on top of each other. If the ink was always just one layer thick, then the total area of S/2 would be less than or equal to the area of the square, which is 1. But the total area is bigger than 1. So the ink must be at least two layers thick at some point. Another way of saying this is that there must be points P and Q of S such that P-Q is a lattice point. I'll leave it to you to use properties (a) and (b) to show that S contains a lattice point other than (0,0). (Of course you should also translate all this stuff about ink and plastic into a real proof). - Doctor Wilkinson, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/