34
$\begingroup$

So, the full problem goes like this:

There are $25$ people at a party. Assuming that among any three people, at least two of them know each other, prove that there exists one person who must know at least twelve people.

I've been stuck on this problem for a while and haven't really figured out how to proceed. I'm pretty sure that there is an answer that can be found via the pigeonhole principle or some graph theory, but I'm not really sure how to get started. Any help would be appreciated.

|cite|improve this question
$\endgroup$
  • 5
    $\begingroup$ Is knowing symmetric. I.e., if A knows B, can we be sure that B knows A? $\endgroup$ – paw88789 Sep 13 '17 at 14:47
  • 2
    $\begingroup$ @paw88789 yes $\,$ $\endgroup$ – Zubin Mukerjee Sep 13 '17 at 14:48
99
$\begingroup$

If everyone knows everyone, then you are done.

Otherwise choose two people, A and B say, who don't know each other. These two people are part of $23$ triples. In each of these triples, either A knows the third person, or B knows the third person.

Thus one of A or B knows (at least) $12$ people.

|cite|improve this answer
$\endgroup$
  • 6
    $\begingroup$ brilliant! $\,$ +1 $\endgroup$ – Zubin Mukerjee Sep 13 '17 at 15:02
  • 6
    $\begingroup$ And that is indeed a Pigeonhole proof. You can put 22 triples into two pigeonholes such that there are only 11 in each, but the 23rd forces one of them to 12 $\endgroup$ – Monty Harder Sep 13 '17 at 18:35
18
$\begingroup$

Pick a vertex $v$. If $\deg(v) \geq 12$ you are done.

Otherwise $v$ is connected with at most 11 vertices. Let $C$ be the vertices connected to $v$ and $N$ be the vertices not connected to $v$. Note that $N$ has at least $13$ vertices.

Fix one vertex $u \in N$.

Now, for each $w \in N$ look at the group $\{ u, v, w\}$. The only possible edge in this group is $uw$. Therefore, $uw \in E(G)$.

This shows that $u$ is connected to all the other vertices in $N$.

Note The proof is basically the following:

The given condition shows that if you fix one vertex $v$, and you look to all the vertices $N$ which are not connected to $v$, then the induced graph on $N$ is the complete graph.

So if $|N| \geq 13$ you are done, otherwise $|N| \leq 12$ which means $\deg(v) \geq 12$.

|cite|improve this answer
$\endgroup$
  • 4
    $\begingroup$ Also, this lets you construct a party of $24$ people easily - the union of two complete graphs of size $12$ (or the complement of $K_{12,12}$.) $\endgroup$ – Thomas Andrews Sep 13 '17 at 15:03
  • 1
    $\begingroup$ Please note in your answer that this argument shows that there is not just one but at least $13$ vertices of degree $\ge12.$ I.e., either all vertices have degree $\ge12,$ or else there is a complete graph on $13$ vertices. $\endgroup$ – bof Sep 20 '17 at 9:29
  • $\begingroup$ This answer is much better (simpler and proves more) than the topo voted answer. $\endgroup$ – bof Sep 20 '17 at 9:31
4
$\begingroup$

This one could be done also by Mantel–Turán theorem:

The maximum number of edges in an $n$-vertex triangle-free graph is ${\displaystyle \lfloor n^{2}/4\rfloor .}$

Let $G$ be a graph with $25$ vertices and connect two people iff they don't know each other. Suppose no one knows $12$ people, then the degree of each vertex is at least $13$ and thus the number of all edges is $\varepsilon$ where

$$ 2\varepsilon = \sum _{i=1}^{25} d_i \geq 25\cdot 13 \Rightarrow \varepsilon \geq {25\cdot 26\over 4}$$

But since this graph is triangle free we have $ \varepsilon \leq {25^2\over 4}$. A contradiction.

|cite|improve this answer
$\endgroup$
3
$\begingroup$

Proof.

Choose two people $P_1$ and $P_2$ who do not know each other (if you cannot, we are done anyway). Now any third person $P$ either knows $P_1$ or $P_2$, because $\{P,P_1,P_2\}$ forms a group of three people and $\{P_1,P_2\}$ cannot be the pair knowing each other. There are $23$ such other people $P$. So by the pidgeonhole principle one of $P_1$ and $P_2$ must know at least $\lceil 23/2\rceil=12$ of them. $\quad\square$

|cite|improve this answer
$\endgroup$
-3
$\begingroup$

Let A is the person who knows 12 people. Now, if there are 12 pairs (12*2) and the A is the third person then A knows at least one of them (pairs) So A knows 12 persons. :)

|cite|improve this answer
$\endgroup$
  • 8
    $\begingroup$ Did you make a typo somewhere? The first sentence in your argument already assumes the claim is true! $\endgroup$ – Erick Wong Sep 13 '17 at 19:27

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.