22
$\begingroup$

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.

$\endgroup$
8
  • 13
    $\begingroup$ If knowing 0 people is ruled out, and knowing oneself is ruled out, then with $n$ people there are only $n-1$ possible numbers of people one can know: one could know 1 other person, 2, other people, …, or all $n-1$ other people. Since there are $n$ people and only $n-1$ different numbers of people they could know, two of them must know the same number of people. This is exactly the pigeonhole principle. $\endgroup$
    – MJD
    Commented Jul 17, 2013 at 3:00
  • $\begingroup$ If you know someone do they necessarily know you? $\endgroup$
    – Sidharth Ghoshal
    Commented Jul 17, 2013 at 3:04
  • $\begingroup$ @MJD Right, exactly, that's basically the short version of what I wrote above. But does this explanation equal a "proof" as the question asks for? If so then that's fine by me! I just felt like there was probably a more formal way to write it :) $\endgroup$
    – CptSupermrkt
    Commented Jul 17, 2013 at 3:09
  • $\begingroup$ @frogeyedpeas Nope not necessarily. A knows B but B doesn't necessarily know A. $\endgroup$
    – CptSupermrkt
    Commented Jul 17, 2013 at 3:09
  • 4
    $\begingroup$ Firstly, +1 for a well-written question that shows your effort. Secondly, the first comment above, by MJD, is a perfectly valid proof. Note one subtle difference between yours and his: you assume that the first person knows $n-1$ people, the second one knows $n-2$ etc., which is hard to justify without some more effort. In the slick way, you just let the number of people known by the first person, second, etc be anything, and just invoke the pigeonhole principle to say you have $n$ numbers taking values in $1$ to $n-1$, so some two must coincide. Anyway this is surely what your teacher wanted. $\endgroup$
    – ShreevatsaR
    Commented Jul 17, 2013 at 3:30

3 Answers 3

Reset to default
19
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ this is not accurate. the minimum is 0 friend. However, if friendship is symmetric, we can't have both goer A with 0 friend and goer B with n-1 friend. Thus either way the number of pigeonhole is n-1. $\endgroup$
    – OMGPOP
    Commented Oct 30, 2013 at 11:08
  • 4
    $\begingroup$ In the original question it was stated as an assumption that the minimum number of friends is 1 by the statement "given that every person at the party knows at least one person". It's possible to prove the same claim without that assumption, but since I was free to use it, I did. $\endgroup$
    – Christian Bueno
    Commented Nov 4, 2013 at 2:59
  • 1
    $\begingroup$ Tell me how will you prove it without that assumption......I have counter example ... $\endgroup$
    – IMO 2021 GOLD
    Commented Feb 11, 2020 at 8:50
3
$\begingroup$

There are two cases to consider:

  1. 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.
  2. 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.

$\endgroup$
1
  • $\begingroup$ The second case is unnecessary because it is given that each person knows atleast one person $\endgroup$
    – Qui Gonn Jinn
    Commented Jul 5, 2021 at 13:29
0
$\begingroup$

For every person in the group, the number of acquaintances is either $0$, or $1$, or $2$, or ... , or $n - 1$.

Let us first assume that no two persons have the same number of acquaintances, so that each of the $n$ numbers, $0$ to $n - 1$, is represented.

But since the presence of $0$ means that there is a person acquainted with no one, and the presence of $n - 1$ means that there is a person acquainted with everyone, then our assumption that no two persons have the same number of acquaintances leads to a contradiction. This assumption is untenable. We are forced to conclude that there are two persons with the same number of acquaintances.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .