# Minimum points to choose from a set such that midpoint is also in the set

Consider the set $S =\{ (x, y)$ : $x$ and $y$ are integers $\}$. The midpoint of a pair of points $P_1$ = ($x_1$, $y_1$) and $P_2$= ($x_2$ , $y_2$ ) is $( \frac{x_1 + x_2}{2}, \frac{y_1+y_2}{2} )$

The minimum number of points one should pick from $S$ to ensure that at least one pair of points has their midpoint also in $S$, is

How to approach this problem? I'm getting minimum points to be 4. Is this correct?

• What is the function $f$ here? – John Hughes Feb 21 '15 at 14:00
• Sorry that was a mistake. Have changed the question correctly @JohnHughes – N S Feb 21 '15 at 14:02

Assuming you've mis-written the definition of $S$, and it's just all ordered pairs of integers, then answer is 5. Consider just $x$-coordinates: once you have two of the same parity (both even, both odd), their average will be an integer. The same goes for the $y$-coordinates.
But you need the average to be an integer for both $x$ and $y$ at the same time. All you now need to do is write down all possibilities in the form $$(O,O)\\ (O, E)\\ (E, O)\\ (E, E)$$ If any one of these appears twice in your set, you're done. If you have just the first three, then you're NOT done. But if you have all 4, then there are still no pairs whose average is in $S$. To be concrete: the four points $(0,0), (1, 0), (0, 1),$ and $(1,1)$ have the property that no average of two of them has integer coordinates.
But if you add one more pair, it'll have to match one of these four, so you've found a pair whose average is in $S$.
[Apologies for writing "4" before -- I mis-read your question as "what's the largest number of points you can have with NO averages being in $S$?"]
• $4$ is not enough. The set $\{0,1\}\times\{0,1\}$ contains four points, and neither midpoint has integer components. – Henning Makholm Feb 21 '15 at 14:06