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?


2 Answers 2


You have shown that $A$ and $B$ have at least $35$ mutual acquaintances. Let $C$ be one of them. If $C$ knows any of the other $34$, then we have a group of four who all know each other. In order to avoid such a group, $C$ can know at most $98-34=64$ members (including $A$ and $B$), but it is given that $C$ knows at least $67$ members.

  • 1
    $\begingroup$ Basically using pigeonhole principle twice, nice. $\endgroup$
    – Hendrix
    Oct 26, 2019 at 3:34
  • 2
    $\begingroup$ Actually C knews A and B and at least other 65 persons. But it works the same. $\endgroup$ Oct 26, 2019 at 5:56

You can also use the Turan theorem. Suppose there is no such 4, then there is at most $${99^2\over 3}$$ acquaintances. But on the other hand we have by handshake lemma at least $${99\cdot 67\over 2}$$ acquaintances.

So we have $${99\cdot 67\over 2} \leq {99^2\over 3} \implies 67\cdot 3\leq 99\cdot 2$$

A contradiction!


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .