Prove that there are 3 girls and 3 boys such that either they know or they don't know each other

Question

I'm struggling to find a solution to this exercise:

Consider a set of 65 girls and a set of 5 boys. Prove that there are 3 girls and 3 boys such that either every girl knows every boy or no girl knows any of the boys.

I know I should use the Ramsey Theorem but I have no idea on how to apply it.

The only solution I came out with is that there are 8 girls all knowing or not knowing 3 boys. However, this doesn't sound right to me because the exercise clearly talks about 3 girls.

Answer 1

Name the boys $A_1,...,A_5$. Now for every girl let $(x_1,x_2,...,x_5), x_i=0$ or $1$ represent if she knows or doesn't know the corresponding boy. You have at most $2^5=32$ such possible vectors and $65=2*32+1$ total vectors. Now you can conclude that at least $3$ of these vectors are equal by the pigeonhole principle. Finally a vectors contains either at least $3$ zeroes or $3$ ones.

Answer 2

You only need 41 girls. Then either 21 girls each know 3 boys, or 21 each don't know 3 boys. There are ten trios of 3 boys, so one of the trios is known/not known to 3 girls.