In a party of n people, certain pairs of people shake hands with each other. In any group of k people, there exists at least one person who shakes hands with all other persons in that group. What is the minimum number of handshakes that can take place at the party?
The problem is inspired from a contest question which I want to solve in general. Here are my attempts in solving the problem:
There are possible groups. In each group, the minimum number of handshakes is . So, at first I thought the answer should be . But I realized that the maximum number of handshakes is . So, I was highly over counting.
Then, I tried for small cases. For and , we have 4 people A,B,C,D. And there are 4 groups of 3. We take the first group (A,B,C) where A shakes hands with B and C. Then in the groups (A,B,D) and (A,C,D), B and D shake hands with D. So, we have a total of 4 handshakes as minimum in this case. From here, I think it's not easy to find the minimum for even small cases.
So, how to solve the problem?