There are four possible coordinate parities (even, even), (even, odd), (odd, even), (odd, odd) Among five points two must have the same parity. Between

There are four possible coordinate parities (even, even), (even, odd), (odd, even), (odd, odd) Among five points two must have the same parity. Between two points of same parity the difference has the parity (even, even). As (even, even) is divisible by two there's an integer midpoint.