I've been working through some pigeonhole principle problems and have some issues with this one. While in general working out more examples gives better intuition/toolkit, I feel like pigeonhole is still rather hit or miss, especially in the case of geometry for me.

The question is as follows: we have $3n+1$ points given in the plane, with the added condition that for any $4$ of these points there are $2$ of them at distance at most $1$. We need to show that $n+1$ fit in a disc of radius $1$.

Any general tips for tackling these types of problems are much appreciated as well.

  • $\begingroup$ $3n+1$ easily gives away the hint that you should consider $3$ holes. If you consider distributing $3n+1$ pigeons into $3$ holes, by pigeonhole principle do you see one hole will contain atleast $n+1$ pigeons ? $\endgroup$ – rsadhvika Feb 18 '18 at 11:01
  • $\begingroup$ Ah ok. So we just take $3$ arbitrary points and consider the discs about them with radius $1$ to be our holes. Now if we assume these discs to be disjoint then all remaining points (our pigeons) by construction will need to be in one of these discs. And as you said, by the pigeonhole principle we are done. Edit: disjoint is not needed, but the 3 points can only be in their own disc for this to work. So I only need to check the case if this is not possible to choose. $\endgroup$ – R. Morty Feb 18 '18 at 11:19
  • $\begingroup$ Yes, I hope you see why we cannot have more than 3 holes - With 4 holes, the given condition fails as you can pick one point from each of the 4 holes such that none of the pairs are with in 1 unit. You can have 3 points that are far away from each other, but you cannot have 4 points. So when you plot all the points with the given condition, you get at most 3 groups... $\endgroup$ – rsadhvika Feb 18 '18 at 11:25
  • $\begingroup$ Alright, cheers! The case where no $3$ points exists that are not in each other's disc works exactly the same way trivially. If $3$ do exist however you need to pick a triple like that if I'm not mistaken. Thanks for the tip, I always feel silly with not getting problems like this because answers are rarely more than a couple of lines. $\endgroup$ – R. Morty Feb 18 '18 at 11:35
  • $\begingroup$ No problem :) Just so you know, I had to consider lot of methods(including incuction!) before seeing that easy hint. While trying induction, at induction step, I realized that you cannot have more than 3 groups. You dont have to feel silly when you don't see a good approach to the problem right away. Nobody does... $\endgroup$ – rsadhvika Feb 18 '18 at 11:53

Your Answer

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

Browse other questions tagged or ask your own question.