Problem - 01 - National Math Camp 2021 Combinatorics Test - "Points not maintaining social distance"

Discussion on Bangladesh National Math Camp
User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:
Problem - 01 - National Math Camp 2021 Combinatorics Test - "Points not maintaining social distance"

Unread post by Anindya Biswas » Fri Apr 30, 2021 5:14 pm

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

User avatar
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"

Unread post by Mehrab4226 » Fri Apr 30, 2021 8:28 pm

Let us assume that there is no circle with a radius of $1$ unit which has more than $9$ points from $S$ in it. Now let us take the leftmost point of $S$ in the plane and take it as a centre and draw a circle of radius $1$. Now at most $8$ other points can be inside the circle. That means there are at least $10$ other points outside the circle. Now again take the left most of the points outside the circle we have just drawn. And we now draw another circle with a radius $1$ with that point as the centre. The new circle can have at most $8$ points that are not present in our first circle. So now we have a point in $S$ that are not in any of the $2$ circles we have drawn. But If we take that rogue point and the centre of the $2$ circles then $2$ points of those $3$ must have a distance less than $1$ meaning the rogue point should be inside any one of the $2$ circles. A contradiction.
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é

Nayer_Sharar
Posts:16
Joined:Mon Dec 21, 2020 9:26 pm

Re: Problem - 01 - National Math Camp 2021 Combinatorics Test - "Points not maintaining social distance"

Unread post by Nayer_Sharar » Wed Jul 14, 2021 11:18 am

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

Post Reply