BdMO Online Forum

The Official Online Forum of BdMO
https://matholympiad.org.bd/forum/

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

https://matholympiad.org.bd/forum/viewtopic.php?f=14&t=6286

Page 1 of 1

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

Posted: Fri Apr 30, 2021 5:14 pm
by Anindya Biswas
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$.

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

Posted: Fri Apr 30, 2021 8:28 pm
by Mehrab4226
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.

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

Posted: Wed Jul 14, 2021 11:18 am
by Nayer_Sharar
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
All times are UTC+06:00
Page 1 of 1
Powered by phpBB® Forum Software © phpBB Limited
https://www.phpbb.com/