1
$\begingroup$

There are 10 people at a party and each person knows an even number of people at the party. Prove that there are 3 people who know the same number of people. Here we assume that knowing someone is reciprocal, that is if person $a$ knows person $b$, then $b$ also knows $a$

I want to use the pigeon-hole principle for this , Now for each of this 10 people, one will know $2,4,6$ or $8$ people right ? Because a person can't know all 10 people, is it true that a person knows himself ? so we can add 10 to the list? also can we add zero as even number to this list ?

Now the result is obviously true if all 10 people knows exactly 2 people. or 4 people,.... etc.

Now to prove that there are always 3 people who know the same number of people, let's assume otherwise (By contradiction).

Let's assume that all $10$ people knows different number (even) of people in the party.

$$2 \space \space \space \space \space \space 4 \space \space \space \space \space \space 6 \space \space \space \space \space \space 8$$

So now we treat these $4$ even numbers as pigeon-holes and we treat the $10$ people as pigeons.

We can assign the first $4$ people to different holes.

$$2 \space \space \space \space \space \space 4 \space \space \space \space \space \space 6 \space \space \space \space \space \space 8$$

$$ \large{\circ} \space \space \space \space \large{\circ} \space \space \space \space \space \large{\circ} \space \space \space \space\large{\circ} $$

Here the small circles represents people.

Now we can do the same thing with the next $4$ people so we will have

$$2 \space \space \space \space \space \space 4 \space \space \space \space \space \space 6 \space \space \space \space \space \space 8$$

$$ \large{\circ} \space \space \space \space \large{\circ} \space \space \space \space \space \large{\circ} \space \space \space \space\large{\circ} $$

$$ \large{\circ} \space \space \space \space \large{\circ} \space \space \space \space \space \large{\circ} \space \space \space \space\large{\circ} $$

Now we are left with $2$ people, and it's clear that assigning any of these $2$ people with any of the holes will result with one hole having $3$ people.

and so we are done ?

Is my reasoning correct ?

The problem is if we add $0$ as a hole or $10$ as a hole, then we are not able to prove it right ?

Because at this point, we will have $5$ holes and $2$ people in each hole and we will have no hole with $3$ people.

$\endgroup$
2
$\begingroup$

You have the right general idea, but it’s a little trickier, because $0$ is a possibility. (You’re right that $10$ is not, since we don’t count anyone as knowing himself.) If there are three people who know no one else at the party, you’re done, so suppose that there are at most two such people.

  • If there are two such people, each of the other eight people must know $2,4$, or $6$ people at the party; why? Now apply the pigeonhole principle to them.

  • If there is one such person, each of the other nine people must know $2,4,6$, or $8$ people at the party; why? Again, apply the pigeonhole principle to them.

And you’ve already covered the case in which everyone knows someone else at the party.

$\endgroup$
5
  • $\begingroup$ OK this makes sense, But when you said that I have covered the case in which everyone knows someone else at the party. What do you mean by that ? $\endgroup$ – alkabary Oct 3 '15 at 18:45
  • $\begingroup$ And I don't understand, why if we add $0$ then one of the holes must contain $3$ people. ? $\endgroup$ – alkabary Oct 3 '15 at 18:46
  • $\begingroup$ @alkabary: Your answer was based on the assumption that the only possibilities are $2,4,6$, and $8$, which is true when everyone at the party knows someone else at the party. When $0$ is a possibility, you have to make separate arguments for the case in which one person knows $0$ and the case in which two people know $0$; I gave hints for those arguments in the two bullet points in my answer. $\endgroup$ – Brian M. Scott Oct 3 '15 at 18:49
  • $\begingroup$ AHAAA, Awesome. I got it :) thanks a lot $\endgroup$ – alkabary Oct 3 '15 at 19:08
  • $\begingroup$ @alkabary: Great; you’re welcome! $\endgroup$ – Brian M. Scott Oct 3 '15 at 19:10
0
$\begingroup$

Yes, that is correct, it could be more rigorous

$\endgroup$
4
  • $\begingroup$ can you show how can it be more rigorous ? $\endgroup$ – alkabary Oct 3 '15 at 18:35
  • $\begingroup$ It’s not quite correct: see my answer. $\endgroup$ – Brian M. Scott Oct 3 '15 at 18:38
  • $\begingroup$ @Brian For an elementary proof, you can assume 0 is not a possibility, however, for a more rigorous proof, 0 must be accounted for $\endgroup$ – JIM KONG Oct 3 '15 at 18:40
  • $\begingroup$ @JIMKONG: Not true. $0$ is a possibility, and an argument that does not account for simply does not answer the question. $\endgroup$ – Brian M. Scott Oct 3 '15 at 18:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.