Problem - 01 - National Math Camp 2021 Combinatorics Test - "Points not maintaining social distance"
- Anindya Biswas
- Posts:264
- Joined:Fri Oct 02, 2020 8:51 pm
- Location:Magura, Bangladesh
- Contact:
![](./images/icons/smile/alert.gif)
You have a set $S$ of $19$ points in the plane such that given any three points in $S$, there exist two of them whose distance from each other is less than $1$. Prove that there exists a circle of radius $1$ that encloses at least $10$ points of $S$.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
— John von Neumann
— John von Neumann
- Mehrab4226
- Posts:230
- Joined:Sat Jan 11, 2020 1:38 pm
- Location:Dhaka, Bangladesh
Re: Problem - 01 - National Math Camp 2021 Combinatorics Test - "Points not maintaining social distance"
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré
-Henri Poincaré
-
- Posts:16
- Joined:Mon Dec 21, 2020 9:26 pm
Re: Problem - 01 - National Math Camp 2021 Combinatorics Test - "Points not maintaining social distance"
Let $G$ be a graph with $19$ vertices and by an edge between any two vertices we mean that they are less than. $1 $ unit apart.
Let $G'$ be the complement of the graph $G$. Then that means in $ G' $,an edge between any two points means that they are At least $1$ unit apart. Now ATQ there cannot be any clique of size $3$ in $G'$( otherwise tat would imply that we would get a triangle in
$G$ with no edge which is impossible)
SO By Turan's theorem ,$G'$ can have AT most $\dfrac{1}{2}×\dfrac{19^2}{2} \sim 90$ edges. That means $G$ has $\geq 19C2-90$ edges $=81$ edges
By handshake lemma ,sum of degree of vertices $\geq 81×2= 162 $
By pigeonhole principle there must exist a vertex in $G$ with at least degree $ \dfrac {162}{19} \sim 9$
WLOG suppose that vertex is $V$ Now draw a circle with radius $1$ with centre $V$ . So at least $9$ other points are enclosed by that circle
Let $G'$ be the complement of the graph $G$. Then that means in $ G' $,an edge between any two points means that they are At least $1$ unit apart. Now ATQ there cannot be any clique of size $3$ in $G'$( otherwise tat would imply that we would get a triangle in
$G$ with no edge which is impossible)
SO By Turan's theorem ,$G'$ can have AT most $\dfrac{1}{2}×\dfrac{19^2}{2} \sim 90$ edges. That means $G$ has $\geq 19C2-90$ edges $=81$ edges
By handshake lemma ,sum of degree of vertices $\geq 81×2= 162 $
By pigeonhole principle there must exist a vertex in $G$ with at least degree $ \dfrac {162}{19} \sim 9$
WLOG suppose that vertex is $V$ Now draw a circle with radius $1$ with centre $V$ . So at least $9$ other points are enclosed by that circle