3

In the café, 4 people are having lunch, whose names are $v_1$, $v_2$, $v_3$, and $v_4$. Some of them know each other. The number of acquaintances of person $v_i$ (who are in the café) is denoted by $d(v_i)$. Prove that among the numbers $d(v_1)$, $d(v_2)$, $d(v_3)$, and $d(v_4)$, there are equal ones.

I guess I have to apply pigeonhole principle here. The possible values for $d(v_i) \in {0, 1, 2, 3}$ (it is a possibility some have zero acquitances and you can't be acquitances with yourself). Therefore, there are 4 possible values and 4 people. And to apply pigeonhole principle we must have $n$ items put into $m$ containers, with $n > m$. How do I work it out?

Geoffrey Trang
  • 9,959
gujaral
  • 159
  • 3
    Hint: if $d(v_i)=3$ for some $i$, is it possible for $d(v_j)$ to be $0$ for any $j$? – lulu Mar 08 '24 at 17:18
  • You can't have $d(v_i) = 0$ and $d(v_j) = 3$. If $d(v_i) =0$ then $v_j$ is unaquainted with $v_i$ and $d(v_j) \ne 3$. And if $d(v_j) =3$ then $v_j$ is acquainted with $v_i$ and $d(v_i) \ne 0$. – fleablood Mar 08 '24 at 17:19
  • 1
    Define a graph with the four people as the vertices and the acquaintances as the edges. Then, with this interpretation, $d(v_i)$ would just be the degree of vertex $v_i$, and then the problem would become an instance of the fact that any undirected graph with at least two vertices must have two vertices with the same degree. – Geoffrey Trang Mar 08 '24 at 17:42

2 Answers2

2

Clearly, $d(v_i) \in {0,1,2,3}$.
Now, number of $d(v_i)$ = $o$ is $0$ or $1$ or $2$.

Case 1 : number of $d(v_i) = o$ is $0$.
$\implies d(v_1),d(v_2),d(v_3),d(v_4)$ $\in$ {1,2,3}.
Thus, we are done.

Case 2 : number of $d(v_i) = o$ is $1$.
without loss of generality, assume $d(v_4) = 0.$
$\implies d(v_1),d(v_2),d(v_3)$ $\in$ {1,2}.
Thus, we are done.

Case 3 : number of $d(v_i) = o$ is $2$.
without loss of generality, assume $d(v_3),d(v_4) = 0.$
$\implies d(v_1),d(v_2)$ $\in$ {1}.
Thus, we are done.

Akshat Mishra
  • 354
1

In fact, the proof makes more sense if we generalize the claim and apply induction.

Generalized claim. Suppose there are $n$ people in the cafe ($n \ge 2$). Show that at least two of them have the same number of acquaintances among this group.

Proof. For $n = 2$, either they are not acquaintances and $d(v_1) = d(v_2) = 0$, or they are acquaintances and $d(v_1) = d(v_2) = 1$.

Now suppose there exists some $m$ such that the claim is true for $n = m$. Then consider the case $n = m+1$. We know that for each person $i$, $d(v_i) \in \{0, \ldots, m\}$. If there exists no person for whom $d(v_i) = 0$, then there are $m+1$ people but $m$ possible numbers of acquaintances, and by the pigeonhole principle, two must share the same number of acquaintances. And if there is more than one person who knows nobody else, then the claim is trivially satisfied: $d(v_i) = d(v_j) = 0$ for some $i \ne j$.

So suppose there is exactly one person for whom $d(v_i) = 0$. Then excluding this person, the remaining people form a set of $m$ people, and by the induction hypothesis, there must be two of them who have the same number of acquaintances. So if the claim is true for $n = m$, then it is true for $n = m+1$, and this concludes the proof.

heropup
  • 135,869