Prove that at a party with at least two people, there are two people who know the same number of people...
Okay, now, I really want to solve this on my own, and I believe I have the basic idea, I'm just not sure how to put it as an answer on the homework. The problem in full:
"Prove that at a party with at least two people, that there are two people who know the same number of people there (not necessarily the same people - just the same number) given that every person at the party knows at least one person. Also, note that nobody can be his or her own friend. You can solve this with a tricky use of the Pigeonhole Principle."
First of all, I'm treating the concept of "knowing" as A can know B, but B doesn't necessary know A. e.g. If Tom Cruise walks into a party, I "know" him, but he doesn't know me.
So what I did first was proved it to myself using examples of a party with 2 people, 3 people, 4 people, and so on. Indeed, under any condition, there is always at least a pair of people who know the same number of people.
So if we define $n$ as the number of party goers, then we can see that this is true under any circumstance if we assume that the first person knows the maximum number of people possible, which is $(n-1)$ (as a person can't be friends with himself). Then since we're not interested in a case where the second person knows the same number of people (otherwise there's nothing to prove), we want the second person to know one less than than the first, or $(n-2)$, and so on.
Eventually we reach a contradiction where the last person knows $(n-n)$, or 0. Since 0 is not a possible value as defined by the problem, that last person must know any number of people from 1 to $(n-1)$, which equals the number of people that at least one other person knows.
Now...I hope that this is the "right idea." But how can I turn this "general understanding" into an answer for a problem that begins with the word "prove?"
Let me note that we only very briefly touched on the concepts of induction and the pigeonhole principle, and did not go into any examples of how to formally "prove" anything with the pigeonhole principle. We did touch on proving the sum of numbers by induction, but that's all as far as induction goes.
Also: Combinatorics question: Prove 2 people at a party know the same amount of people does not really work for me, because
A) we've not talked about "combinatorics", and
B) that question allows for someone to know 0 people.
Let $n$ be the number of party-goers. The maximum number of people a person can know is $n-1$ and the minimum number he/she can know is 1 (by assumption), giving us $n-1$ possibilities for the number of people someone can know. Every single person must be assigned one of these $n-1$ possible numbers but since there are $n$ party-goers one of these numbers must be used twice due to the pigeonhole principle i.e. two party-goers know the same number of people.
There are two cases to consider:
- Assume there is a someone at the party, lets say Joe, who knows everyone else at the party. He must know $n-1$ people. In this case, everybody else at the party must know at least know Joe, and the minimum number of people a person can know is $1$. This gives us the set $\{1, 2, ... n - 1\}$ which represents the possible number of people each person can know.
- Assume there is a party crasher, Harry, who doesn't actually know anybody. This means that even a socialite like Joe can't possibly know everyone, so the maximum number of people a person can know is $n - 2$. This gives us the set $\{0, 1, ..., n - 2\}$.
Both these sets have n-1 elements. Since there are $n$ people at the party, and $n-1$ possibilities for the number of people each person can know, it follows that there must be at least two people who know the same number of people.