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.
Best Answer
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.