8
$\begingroup$

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?

$\endgroup$
11
$\begingroup$

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.

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

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.