# Hall's marriage theorem question.

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?

• 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. – saulspatz Jul 26 at 16:03
• That's rather interesting, how would you do that? – vpam Jul 26 at 16:13
• I don't know. That was just a comment. – saulspatz Jul 26 at 16:16

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.