2
$\begingroup$

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.

$\endgroup$

2 Answers 2

Reset to default
6
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Wait a second, those 2 vectors aren't meant to be either 0 or 1? I don't understand that step there $\endgroup$
    – philip613
    Commented May 3, 2019 at 17:55
  • $\begingroup$ @philip613 He only need 3 girls that know all three boys (or none of them) so you need that vector to contain either 3 zeroes or 3 ones $\endgroup$
    – Μάρκος Καραμέρης
    Commented May 3, 2019 at 21:02
2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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$. $\endgroup$
    – bof
    Commented May 4, 2019 at 5:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .