There are $100$ members in a ladies' club.Each lady has had tea (in private) with exactly $56$ of her lady friends.The Board,consisting of the $50$ most distinguished ladies,have all had tea with one another.Prove that the entire club may be split into two groups in such a way that,with in each group,any lady has had tea with any other.
Problem
Source: Baltic Way 2015
Tags: combinatorics
08.11.2015 21:15
Let the ladies be vertices. Let an edge represent that two ladies have had tea together. Note we want the degree of each vertex to be exactly $56$ If we consider only the Board by itself, each vertex in it has degree $49$ Thus there are exactly 7 edges for each member of the board coming out of the Board into the other group of $50$, so $350$ in total. Consider the Others (everyone other than the Board). The Others must have a total degree of $50*56=2800$. Thus if we consider the others by themselves, we must remove the edges coming out from the Board into the Others. So the total degree of the Others, after completely removing the Board, must be $2450$ But the only way this is possible is if every person in the Others has had tea with every other person in the others ($50*49=2450). Thus they can be split into the Board and the Others.
10.11.2020 11:33
Let $A$ be the set of Distinguished Ladies and $B$ be the set of rest of them. Among ladies in $A,$ each of them has had tea with rest of $49$ of them. So for every $\ell\in A$ has had tea with exactly $7$ of $B$. We claim that reverse is also true. Total matchings of Teas between $A \leftrightarrow B$ are $7\cdot50=350$. Clearly, there is atleast one $\ell\in B$ such that there are $7$ matchings are there from $\ell \mapsto A$. If possible, assume one of ladies, say lady $s$ in $B$ has $\le 6$ matchings to $A$ then $s$ has maximum of $6+49=55$ matchings in total, where $49$ matchings are from $s$ to other elements of $B,$ which is a clear contradiction. Hence there are exactly $7$ matchings from each $\ell \in B$ to $A$. But then to have $56$ matchings in total for ladies in $B$. All ladies in $B$ must match with each other. But then this implies, $A\equiv B$. In both $A$ and $B,$ ladies have had tea with each other. Hence, this is the desired partition of club. $\blacksquare$