2

If there are $6$ people at a party, then either at least $3$ people met each other before the party or at least $3$ people were strangers before the party.

Solution from Xinfeng Zhou's A practical Guide to Quantitative Finance:

Let's say that you are the $6^{th}$ person at the party. Then by generalized Pigeon Hole Principle, among the remaining $5$ people, we conclude that either at least $3$ people met you or at least $3$ people did not meet you. Now let's explore these two mutually exclusive and collectively exhaustive scenarios:

Case 1: Suppose that at least $3$ people have met you before. If two people in this group met each other, you and the pair ($3$ people) met each other. If no pair among these people met each other, then these people ($\ge 3$ people) did not meet each other. In either sub-case, the conclusion holds.

Case 2: Suppose at least $3$ people have not met you before. If two people in this group did not meet each other, you and the pair ($3$ people) did not meet each other. If all pairs among these people knew each other, then these people ($\ge 3$ people) met each other. Again, in either sub-case, the conclusion holds.

My doubt is this:
How can we say that either three people met me, or three did not? I can visualize the pigeon(person from $1$ to $5$) and hole (either met or did not meet), but if we look at the five people present here, each could have independently met or did not meet me.

Kom
  • 123
  • 3
    The pigeonhole principle does not depend on the independence, and is in fact stronger than that (you could have dependence as well). It says here that, if there are 5 pigeons and 2 holes (as you described), at least 1 hole has >= 5/2 = 3 people in it. – algebroo Aug 22 '23 at 15:32
  • Rather than remembering the $+1$ or $-1$ terms in some formulations of the pigeonhole principle, I prefer to go through its (very easy) derivation from scratch: If you knew only 2 of the others and you didn't know only 2 of them, then that makes only 4 others altogether, whereas in fact there are 5 others because you're the 6th. – Andreas Blass Aug 22 '23 at 15:35
  • The answer to your question is here: https://en.wikipedia.org/wiki/Theorem_on_friends_and_strangers – Ethan Bolker Aug 22 '23 at 16:00

1 Answers1

1

Mostly to get this out of the unanswered question line:

If you have n lines, at least half are one color. That shows, that at least 3 of 5 lines drawn from any one person, have to be one of the two colors. It then follows, that you can't connect the three with that color line; or you'd make a triangle with those 3. If you connect them all with the opposite color you form the triangle of the opposite color. The relations described by the lines, are symmetric.

Roddy MacPhee
  • 859