I am aware of the proof - Given that there are $n$ people in a party $\left(~\mbox{where}\ n \geq 2~\right)$, there are $2$ people who know the same number of people.
Assuming:
- knowledge is mutual so if A knows B, B also knows A
- knowing oneself is not counted
. .
Where the proof goes as follows:
- Case 1: There is someone who knows everyone $\left(n-1\right)$ people in the party so range is $\bf\left[1,n - 1\right]$.
- Case 2: There is nobody who knows everyone in the party so range is $\bf\left[0,n - 2\right]$.
In either case, the pigeonhole principle says there are two that match.
. .
My question is: In the specific scenario where the number of people (n) is equals to 2 then, according to this proof it shows that these 2 people who are the only ones at the party both know the same number of people which is 1. From here, can I conclude that these 2 people actually know each other?
So not only do these 2 people know the same number of people BUT is it correct to say that they also know the SAME people (assuming people are distinguishable) ?
If this is the case, it is just really puzzling to me that the pigeonhole principle is able to come to a conclusion by itself almost magically that 2 people actually know each other..
The theorem doesn't assert that they know each other. It states that they know the same number of people. If they know each other, this number is 1; if they don't know each other, it's 0.