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?

  • $\begingroup$ What is the function $f$ here? $\endgroup$ – John Hughes Feb 21 '15 at 14:00
  • $\begingroup$ Sorry that was a mistake. Have changed the question correctly @JohnHughes $\endgroup$ – 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$?"]

  • $\begingroup$ But the answer given is 5. I'm missing something. And can you share your approach? I've done very naively by taking a small example. @John Hughes $\endgroup$ – N S Feb 21 '15 at 14:04
  • $\begingroup$ $4$ is not enough. The set $\{0,1\}\times\{0,1\}$ contains four points, and neither midpoint has integer components. $\endgroup$ – Henning Makholm Feb 21 '15 at 14:06
  • $\begingroup$ You beat me to it, Henning. I should've had that second cup of tea before writing. $\endgroup$ – John Hughes Feb 21 '15 at 14:08
  • $\begingroup$ @JohnHughes Thanks for such a beautiful explaination. $\endgroup$ – N S Feb 21 '15 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.