The argument doesn't depend on n. So if the final conclusion is not possible, an earlier assumption must fail.
If n=4, you won't find four pairs with different common parity type and same midpoint.
Maybe it's time to consider the four-coloring induced by parity types: take a chessboard pattern, and in each other row, replace black and white by red and blue.