একটা পার্টিতে $11$ জন আছে। এদের মধ্যে কেউ কেউ পরস্পরের সাথে হ্যান্ডশেক করে। এই পার্টিতে যেকোনো তিনজনের মধ্যে এমন একজন আছে যে ওই তিনজনের বাকি দুইজনের সাথে হ্যান্ডশেক করে। ওই পার্টিতে সর্বনিম্ন কতগুলো হ্যান্ডশেক হতে পারে?
In a party of $11$ people, certain pairs of people shake hands with each other. In every group of three people, there exists one person who shakes hands with the other two. What is the minimum number of handshakes that can take place at this party?
BdMO National Secondary 2020 P3
This section is intentionally left blank.
-
Anindya Biswas
- Posts:264
- Joined:Fri Oct 02, 2020 8:51 pm
- Location:Magura, Bangladesh
- Contact:
Re: BdMO National Secondary 2020 P3
Let's consider the peoples as vertices and handshakes as edges of a graph. We will connect $A$ and $B$ with an edge if $A$ handshakes with $B$. So this graph has $11$ nodes.
Now, we will take the complete graph with $11$ vertices and start removing edges in such a way that each triplet of vertices contains at least two edges after removing those edges. We have to remove highest number of edges in order to get to the minimum number of edges required.
Here's an important observation:
Let's assume we removed the edge $AB$. Now we cannot remove any other edge that contains the vertex $A$ or $B$.
Proof of this observation:
Let's assume we removed the edge $AB$ and $AX$. Then the triange $AXB$ would contain at most one edge. Which contradicts the fact that every triangle (Here triangle means triplet of vertices) will contain at least $2$ edges. Similarly we also cannot remove a edge that contains the vertex $B$.(Proved)
Now we will call a pair of vertex $A$ and $B$ useless if we removed the edge $AB$, since we cannot remove another vertex that contains $A$ or $B$.
Now, in the process of removing edges, after removing each edge, a pair of vertex becomes useless. So, after removing $5$ edges, $10$ vertices become useless and we are left with only one vertex and we cannot remove any other edge.
So, highest number of edges we can remove is $5$. So we are left with $^{11}C_{2}-5=55-5=50$ edges. Which is the minimum number of handshakes that can take place in the party.
Now, we will take the complete graph with $11$ vertices and start removing edges in such a way that each triplet of vertices contains at least two edges after removing those edges. We have to remove highest number of edges in order to get to the minimum number of edges required.
Here's an important observation:
Let's assume we removed the edge $AB$. Now we cannot remove any other edge that contains the vertex $A$ or $B$.
Proof of this observation:
Let's assume we removed the edge $AB$ and $AX$. Then the triange $AXB$ would contain at most one edge. Which contradicts the fact that every triangle (Here triangle means triplet of vertices) will contain at least $2$ edges. Similarly we also cannot remove a edge that contains the vertex $B$.(Proved)
Now we will call a pair of vertex $A$ and $B$ useless if we removed the edge $AB$, since we cannot remove another vertex that contains $A$ or $B$.
Now, in the process of removing edges, after removing each edge, a pair of vertex becomes useless. So, after removing $5$ edges, $10$ vertices become useless and we are left with only one vertex and we cannot remove any other edge.
So, highest number of edges we can remove is $5$. So we are left with $^{11}C_{2}-5=55-5=50$ edges. Which is the minimum number of handshakes that can take place in the party.