Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Pigeonhole Principle

  1. Apr 7, 2010 #1
    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
  2. jcsd
  3. Apr 7, 2010 #2
    Let K(a) be the number of acquaintances of a; then, you can only say that [itex]0 \leq K\left(a\right) \leq n-1[/itex]. 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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook