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

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.

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.
• Apparently someone downvoted this answer because they didn't understand it or thought it was expressed too tersely. Let me spell it out in tedious detail. There are $\binom52=10$ trios ($3$-element sets) of boys, call them $T_1,\dots,T_{10}$. Let $A_i$ be the set of girls who know all the boys in $T_i$, and let $B_i$ be the set of girls who know none of the boys in $T_i$. Each girls belongs to (at least) one of the $20$ sets $A_1,B_1,\dots,A_{10},B_{10}$. If there are more than $2\cdot20=40$ girls, then (pigeonhole principle) $3$ of them belong to the same set $A_i$ or $B_i$.