Midpoint Problem

This is a problem I came up with to use in a mock univeristy interview, though it's a nice little problem for students in lower years to play around with.

 Let \(S\subset\mathbb{Z}^2\) and \(M((x_1,y_1),(x_2,y_2))=(\frac{x_1+x_2}{2},\frac{y_1+y_2}{2})\). What is the maximum \(|S|\) such that \(M(x,y)\notin\mathbb{Z}^2\:\forall x, y \in S\)

Or, in a way that's more accessible:

As an extention, you could consider the same problem, but on a 3D grid. Or an nD grid!

Solution:

Consider the parity. If two numbers are even, their midpoint is an integer. Likewise for two odd numbers. One even and one odd, however, has a midpoint which is not an integer. So we need to include coordinates where two coordinates do not have the same parity for both x and y coordinates.

Let's start building our set of coordinates.

A=(odd, odd)

B=(odd, even)

The midpoint of these two would have an integer value for x, but a non-integer value for y, so that's not on the grid.

 C=(even, even)

The midpoint of C and B has integer y, but non-integer x. The midpoint of C and A  has non-integer x and y coordinates.

D=(even, odd)

All midpoints are still off the grid.

We now run out of options. There can only be 4 coordinates. Or, using the product rule for counting, we have 2 options for the parity of the x coordinate and 2 options for the parity of the y coordinate. \(2\times2=4\).

By extension, in 3D we have \(2\times2\times2=8\) or in nD, \(2^n\).