I tried solving this with graph theory. So there are 99 points (each point is a person) and if we draw a line between two points, it will mean those two people knows each other (Since knowing someone is mutual).
So, there are at least $$\frac{99*67}{2}$$ lines and we need to prove there's at least a group of four points where every point is connected with the other three.
Directly, i don't know how to prove it, since there are $\frac{99*98*97*96}{6}$ possible groups of four points, but i don't find anything with this.
So i also tried to see how many groups of three points where all three are connected, because, if another point is connected to these, it will be the group of 4 we're looking for. For this, if we select one point $A$, it will connect with at least 67 points, then, we select one $B$ of those 67. It will connect with at least 66 besides $A$. If we want to have the less posible amount of triangles, then we have to connect $B$ with the points that aren't connected with $A$, and these are 31, but $B$ will have to connect with at least other 36, so there are at least 36 triangles. Now, this only used $A$ and $B$ so there are way more triangles but i don't know how to proceed.
Any suggestions or ideas?
from Hot Weekly Questions - Mathematics Stack Exchange
Post a Comment