Pigeonhole Principle

  • Thread starter kliker
  • Start date
  • #1
104
0

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

  • #2
402
1
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.
 

Related Threads on Pigeonhole Principle

  • Last Post
Replies
5
Views
5K
  • Last Post
Replies
12
Views
4K
  • Last Post
Replies
4
Views
4K
  • Last Post
Replies
8
Views
4K
  • Last Post
Replies
5
Views
4K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
1
Views
1K
Replies
2
Views
2K
Top