In a party with 2000 persons, among any set of four there is at least one person who knows each of the other three. There are three people who are not mutually acquainted with each other. How many total people know everyone at the party? Prove your result. (Assume that "knowing" is not necessarily a symmetric relation; that is, if A knows B then B doesn't necessarily know A).

  • 1
    $\begingroup$ can "not mutually acquanted" mean A knows B but B doesn't know A or does it mean neither A knows B nor B knows A. Also are those 3 people in any set of 4 or just those 3 total? $\endgroup$ – kaine Nov 12 '13 at 21:28
  • $\begingroup$ To answer your first question: "not mutually acquainted" could imply either of the two cases you've proposed. To answer your second question: these are 3 total. $\endgroup$ – David Smith Nov 12 '13 at 21:32
  • $\begingroup$ Sorry to ask again but does that mean among any other set of 3 people, at least two of them know each other? $\endgroup$ – kaine Nov 12 '13 at 21:41
  • $\begingroup$ No worries: it means that of the 2000 persons, there are 3 particular persons who are not mutually acquainted with each other. $\endgroup$ – David Smith Nov 12 '13 at 21:42
  • $\begingroup$ In other words, if you look at all combinations of 3 people, there is exactly one such combination with no pair who both know each other. In all other triplets, you can find (at least) two of them that both know each other. $\endgroup$ – zibadawa timmy Nov 12 '13 at 21:46

I believe the answer can be anything from $0$ to $1997$. Let $a,b,c$ be the people who don't know anybody and $0$ to $1996$ be everybody else. Clearly all the numbered people know all of $a,b,c$. Now let all the numbered people know everybody except the next number up (including $1996$ doesn't know $0$). Every group of four will include at least one person whose upper neighbor is not there, so will have somebody who knows all the other three. We can restore any of the broken links to raise the number who know everybody.

  • $\begingroup$ In your answer, you write, "Let $a,b,c$ be the people who don't know anybody". Don't you mean "Let $a,b,c$ be the people who aren't mutually acquainted with each other"? $\endgroup$ – David Smith Nov 14 '13 at 19:34
  • 1
    $\begingroup$ @DavidSmith: you are correct, but I don't think it changes the argument. They still can't know everybody, and all the numbers need to know all three of them. You could add links of them knowing some or all of the numbers. $\endgroup$ – Ross Millikan Nov 14 '13 at 19:39

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.