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.