0
$\begingroup$

Show that between 50 pianists, 50 vilonists, and 50 guitarists, such that each musician knows atleast 40 other musicians (The relation is symmetric ofcourse), we can find 40 unique triplets of musicians that know eachother.

I was given this question as a practice for Hall's marriage theorem, However, I couldn't bring myself to solve it.

I would like to get some insight on how to do so, also - Could this kind of quesiton be solved using the pigenhole principle?

$\endgroup$
  • $\begingroup$ We can't find triples consisting of one player for each instrument, since it's possible that guitarists know only guitarists, so the three groups must be a red herring. We have to show that among 150 people, each of whom knows 40 people, it's possible to find 40 sets of 3 mutual acquaintances. $\endgroup$ – saulspatz Jul 26 at 16:03
  • $\begingroup$ That's rather interesting, how would you do that? $\endgroup$ – vpam Jul 26 at 16:13
  • $\begingroup$ I don't know. That was just a comment. $\endgroup$ – saulspatz Jul 26 at 16:16
0
$\begingroup$

I don't think this is true. Suppose the musicians are divided into four groups, A,B,C, and D. Nobody knows anyone is his own group. Groups A, B, and C have $40$ members, and group D has $30$. Everyone in group A knows everyone in group B and no one else. Everyone in group B knows all the people in group A, 10 people from group C, and no one else. Everyone in group C knows 10 people from group B, all the people in group D, and no one else. Everyone in group D knows all the people in group C and no one else.

Now since no one knows anyone in his own group, a triple of three mutual acquaintances must comprise a member of each of three different groups. No one from group A can belong to such a triple, for he knows only people from group B. Neither can a person from group D, who knows only people from group C. So, only members of groups B and C can belong to the triples, contradiction.

$\endgroup$

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.