# Pigeonhole Principle

## Main Question or Discussion Point

show that in a set that has n people at least 2 of them have the same amount of acquaintances in the set

well what i tried is that first of all if we have n people one person can know n-1 people within the set so having a set of n people at least 2 of them should have the same amount of acquaintances in the set

but, i dont think its right, maybe someone could guide me please, i would appreciate it

i really think that i havent fully understood how to use this principle here

## Answers and Replies

Related Set Theory, Logic, Probability, Statistics News on Phys.org
Let K(a) be the number of acquaintances of a; then, you can only say that $0 \leq K\left(a\right) \leq n-1$. This is a range of n, which is exactly the number of persons, so you cannot infer (yet) that K(a)=K(b) for some a and b.

Think like this: the function K goes from the set {1,...,n} (persons) to {0,1,...,n-1} (number of acquaintances of each person); if you manage to prove that this function cannot be injective, for n > 1, then you are done.