In the 2-dimensional Cartesian coordinate plane, a lattice point is a point whose x - and y -coordinates are integers.
Consider a set S of N = 2 0 1 8 distinct lattice points. For each pair of distinct points P , Q ∈ S , consider the midpoint m ( P , Q ) . Let X be the number of pairs for which m ( P , Q ) is also a lattice point.
What is the smallest possible value of X ?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Perhaps a simpler way to show that A 2 + B 2 + C 2 + D 2 is minimized when A,B,C, and D are close together would be to show that 1 0 0 9 2 ≤ A 2 + B 2 + C 2 + D 2 by AM-QM (and equality holding when A=B=C=D). Then again maybe my method is not simpler; it is what seemed simpler to me at least.
Log in to reply
You'd prove that A = B = C = D = 5 0 4 2 1 is the minimal solution in real (or even rational ) numbers.
But the fact that A , B , C , D must be integers throws a wrench into this method.
Log in to reply
If we were able to use fractional numbers, we could make A 2 + B 2 + C 2 + D 2 = 1 0 1 8 0 8 1 . Using the close values to 504.5 of 504,504,505,505 gives us A 2 + B 2 + C 2 + D 2 = 1 0 1 8 0 8 2 . Because A 2 + B 2 + C 2 + D 2 = 1 0 1 8 0 8 1 only works for A=B=C=D=504.5, 504,504,505,505 is the next best integer solution (only 1 higher than optimal).
Problem Loading...
Note Loading...
Set Loading...
m ( P , Q ) is a lattice point if and only if x P ≡ x Q and y P ≡ y Q mod 2, that is, if the x -coordinates have equal parity (odd or even) and the y -coordinates have equal parity.
Thus we may partition the set S into four "bins", based on whether the coordinates are even or odd. Label these bins S 1 , … , S 4 , and their size N 1 , … , N 4 . The midpoint of two points taken from different bins is never a lattice point. The midpoints of two points from the same bin is always a lattice point. Therefore X = i = 1 ∑ 4 number of pairs in S i = i = 1 ∑ 4 ( 2 N i ) = i = 1 ∑ 4 2 1 N i ( N i − 1 ) . This sum is minimal if the N i are chosen to be as similar as possible.
Specific solution . With N = 2 0 1 8 this means that N 1 = N 2 = 5 0 4 and N 3 = N 4 = 5 0 5 , so that X = 2 ( 2 5 0 4 ) + 2 ( 2 5 0 5 ) = 5 0 4 ⋅ 5 0 3 + 5 0 5 ⋅ 5 0 4 = ( 5 0 3 + 5 0 5 ) ⋅ 5 0 4 = 5 0 8 0 3 2 .
General solution . Writing N = 4 q + r with 0 ≤ r < 4 , this means that we have r bins of size q + 1 and 4 − r bins of size q , and X = 2 1 q ( q + 1 ) r + 2 1 ( q − 1 ) q ( 4 − r ) = 2 1 q ( 4 q + 2 r − 4 ) = 2 1 q ( N + r − 4 ) . In the case N = 2 0 1 8 we have q = 5 0 4 and r = 2 , so that X = 2 1 ⋅ 5 0 4 ⋅ ( 2 0 1 8 + 2 − 4 ) = 5 0 8 0 3 2 .
Note that for large values of N , the minimum number of pairs with lattice midpoints tends to 4 1 of the total number of pairs.
Proof that the value is minimal if the N i are chosen as similar as possible: suppose that N j > N i . Remove a point from bin S j and add a points to bin S i . Then the number of lattice midpoints they contribute changes by Δ X = [ 2 1 ( N j − 1 ) ( N j − 2 ) + 2 1 ( N i + 1 ) N i ] − [ 2 1 N j ( N j − 1 ) + 2 1 N i ( N i − 1 ) ] = N i − ( N j − 1 ) = 1 − ( N j − N i ) . This is negative if N j > N i + 1 . Therefore we can always reduce the value of X by reducing the number of points in the larger bins and increasing the number of points in the smaller bins until they differ no more than one from each other.