Lattice point

In the 2-dimensional Cartesian coordinate plane, a lattice point is a point whose x x - and y y -coordinates are integers.

Consider a set S S of N = 2018 N = 2018 distinct lattice points. For each pair of distinct points P , Q S , P,Q \in S, consider the midpoint m ( P , Q ) . m(P,Q). Let X X be the number of pairs for which m ( P , Q ) m(P,Q) is also a lattice point.

What is the smallest possible value of X ? X?


Inspiration


The answer is 508032.

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.

1 solution

m ( P , Q ) m(P,Q) is a lattice point if and only if x P x Q x_P \equiv x_Q and y P y Q y_P \equiv y_Q mod 2, that is, if the x x -coordinates have equal parity (odd or even) and the y y -coordinates have equal parity.

Thus we may partition the set S S into four "bins", based on whether the coordinates are even or odd. Label these bins S 1 , , S 4 S_1,\dots,S_4 , and their size N 1 , , N 4 N_1,\dots,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 ( N i 2 ) = i = 1 4 1 2 N i ( N i 1 ) . X = \sum_{i=1}^4 \text{number of pairs in}\ S_i = \sum_{i=1}^4 \binom{N_i}2 = \sum_{i=1}^4 \tfrac12N_i(N_i-1). This sum is minimal if the N i N_i are chosen to be as similar as possible.

Specific solution . With N = 2018 N = 2018 this means that N 1 = N 2 = 504 N_1 = N_2 = 504 and N 3 = N 4 = 505 N_3 = N_4 = 505 , so that X = 2 ( 504 2 ) + 2 ( 505 2 ) = 504 503 + 505 504 = ( 503 + 505 ) 504 = 508 032 . X = 2\binom{504}2 + 2\binom{505}2 = 504\cdot 503 + 505\cdot 504 = (503 + 505)\cdot 504 = \boxed{508\,032}.

General solution . Writing N = 4 q + r N = 4q + r with 0 r < 4 0 \leq r < 4 , this means that we have r r bins of size q + 1 q + 1 and 4 r 4 - r bins of size q q , and X = 1 2 q ( q + 1 ) r + 1 2 ( q 1 ) q ( 4 r ) = 1 2 q ( 4 q + 2 r 4 ) = 1 2 q ( N + r 4 ) . X = \tfrac12q(q+1)r + \tfrac12(q-1)q(4-r) = \tfrac12q(4q + 2r - 4) = \frac12q(N + r - 4). In the case N = 2018 N = 2018 we have q = 504 q = 504 and r = 2 r = 2 , so that X = 1 2 504 ( 2018 + 2 4 ) = 508 032 . X = \tfrac12\cdot 504\cdot (2018 + 2 - 4) = \boxed{508\,032}.


Note that for large values of N N , the minimum number of pairs with lattice midpoints tends to 1 4 \tfrac 1 4 of the total number of pairs.


Proof that the value is minimal if the N i N_i are chosen as similar as possible: suppose that N j > N i N_j > N_i . Remove a point from bin S j S_j and add a points to bin S i S_i . Then the number of lattice midpoints they contribute changes by Δ X = [ 1 2 ( N j 1 ) ( N j 2 ) + 1 2 ( N i + 1 ) N i ] [ 1 2 N j ( N j 1 ) + 1 2 N i ( N i 1 ) ] = N i ( N j 1 ) = 1 ( N j N i ) . \Delta X = \left[\tfrac12(N_j-1)(N_j-2) + \tfrac12(N_i+1)N_i\right] - \left[\tfrac12N_j(N_j-1) + \tfrac12N_i(N_i - 1)\right] = N_i-(N_j-1) = 1 - (N_j-N_i). This is negative if N j > N i + 1 N_j > N_i + 1 . Therefore we can always reduce the value of X 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.

Perhaps a simpler way to show that A 2 + B 2 + C 2 + D 2 A^2+B^2+C^2+D^2 is minimized when A,B,C, and D are close together would be to show that 100 9 2 A 2 + B 2 + C 2 + D 2 1009^2 \leq 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.

John Ross - 3 years, 2 months ago

Log in to reply

You'd prove that A = B = C = D = 504 1 2 A = B = C = D = 504\tfrac12 is the minimal solution in real (or even rational ) numbers.

But the fact that A , B , C , D A,B,C,D must be integers throws a wrench into this method.

Arjen Vreugdenhil - 3 years, 2 months ago

Log in to reply

If we were able to use fractional numbers, we could make A 2 + B 2 + C 2 + D 2 = 1018081 A^2+B^2+C^2+D^2=1018081 . Using the close values to 504.5 of 504,504,505,505 gives us A 2 + B 2 + C 2 + D 2 = 1018082 A^2+B^2+C^2+D^2=1018082 . Because A 2 + B 2 + C 2 + D 2 = 1018081 A^2+B^2+C^2+D^2=1018081 only works for A=B=C=D=504.5, 504,504,505,505 is the next best integer solution (only 1 higher than optimal).

John Ross - 3 years, 2 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...