There were 36 participants at an event. Some of the participants shook hands with each other. But any two participants dindn't shake hands with each other more than once. Each participant recorded the number of handshakes they made. It was found that- any two participants "with the same number of handshakes made" had not shaken hands with each other.

Find the maximum number of incidents of handshakes at the party. (When two participants shake hands with each other, this will be counted as one handshake incident.)

  • 3
    $\begingroup$ Rephrased as asking for the maximum number of edges in a graph $G=(V,E)$ such that $\deg(u)=\deg(v)\implies u\not\sim v$ $\endgroup$ – JMoravitz Jan 17 '17 at 20:39

We can have one person who has shaken hands with $35$ people. Then we can have $2$ people who have shaken hands with $34$ people (but not each other), then $3$ at $33$ handshakes, $4$ at $32$ handshakes, $5$ at $31$ handshakes, $6$ at $30$ handshakes, and $7$ at $29$ handshakes. This leaves $8$ people who are already shaking hands with $28$ people (but not with each other), completing the $36$.

In total, and remembering that above we have counted the handshakes from each end, there are: $$\frac 12( 35+2\cdot34+3\cdot33+4\cdot32+5\cdot31+6\cdot30+7\cdot29+8\cdot28) \\= 546 \text{ handshakes in total}$$

  • $\begingroup$ How can you prove that the solution you made shows the maximum number of Handshakes? $\endgroup$ – Rangan Aryan Jan 21 '17 at 16:38
  • 1
    $\begingroup$ The numbers are maximum at every point. For example, you can't have more than $3$ people making $33$ handshakes, or some of them will have to be shaking hands with each other which is forbidden. $\endgroup$ – Joffan Jan 21 '17 at 16:56
  • $\begingroup$ that was great ! $\endgroup$ – Rangan Aryan Jan 21 '17 at 17:12
  • $\begingroup$ @Joffan: Can you explain why this reasoning also guarantees that there are no other partitionings of the participants into groups (except $1+2+3+4+5+6+7+8$), which may result in more handshakes? $\endgroup$ – Reinhard Meier Jan 22 '17 at 15:29

This is the proof of optimality:

Let $N$ be the number of participants. We form groups of participants that perform the same number of handshakes. Let $n$ be the number of groups. $a_i$ is the number of members in group $i$. Each member in this group performs $b_i$ handshakes. Without loss of generality, we are counting handshakes from each end, looking for the maximum of $$ f(a,b) = \sum_{i=1}^n a_ib_i $$ under the following constraints: \begin{eqnarray*} && \sum_{i=1}^n a_i = N \\ && a_i > 0 \;\forall i\in \{1,\ldots,n\} \\ && a_1\leq a_2\leq \ldots \leq a_n \;\;\text{(WOLOG)} \\ && b_i \geq 0 \;\forall i\in \{1,\ldots,n\} \\ && a_i + b_i \leq N \;\forall i\in \{1,\ldots,n\} \\ && i\neq j \Longrightarrow b_i \neq b_j \end{eqnarray*} Each configuration of $a_i$, which satisfies the topmost three constraints, is called a partition. A partition which additionally satisfies $i\neq j\Longrightarrow a_i \neq a_j$ will be called heterogeneous partition. Each configuration of $a_i$ and $b_i$ satisfying all given constraints is called a party.

Please note that there are partys that cannot be turned into valid instructions saying who should shake hands with whom, because we only look and the number of handshakes, but not at the actual configuration of handshake partners. Example: $n=N=2,\;a_1=a_2=1,\;b_1=0,\;b_2=1$. The member of group 2 must shake hands with the member of group 1, but the member of group 1 must not shake hands with anybody else.

But if we find an optimal party for the weak constraints given above (ignoring that it might be impossible to turn this into actual handshake instructions), and if this optimum also satisfies (by accident) the stronger conditions that everybody finds someone he or she can shake hands with, then this party is obviosly also an optimum of the original problem.

Now we collect some properties of optimal partys. First, we examine the implications of the assumption that the optimal party has a heterogenous partition.

In an optimal party with heterogeneous partition, we obviously have $a_i + b_i = N \;\forall i$, because it would not make sense to choose a smaller number of handshakes for any of the groups. We can also conclude that $a_{i+1} = a_i+1$, because in case of $a_{i+1} > a_i+1$, a member of group $(i+1)$ could make up a group of his/her own with $b_{i+1}$ handshakes, while the number of handshakes of group $i+1$ could be increased to $b_{i+1}+1$. This increases the value of $f$ by $a_{i+1}-1$. We can also conclude $a_1=1$. If $a_1$ was greater than $1$, we could create a new group, taking one member out of each of the existing groups. The number of handshakes in each of the existing groups could be increased by one, and $b_n$ could be chosen as the number of handshakes of the new group. It can be shown that this increases the value of $f$ by $n(a_1-1)$. Therefore, if the optimal party has a heterogeneous partition, this partition must be necessarily $1+2+3+\ldots+n$.

Now we examine the parties with non-heterogeneous partitions, because we have not shown yet, that the optimal solution can be found within the set of partys with heterogeneous partitions.

In an optimal party, there can be only one group $g$ with $a_g+b_g<N$. Assume there were two indices $g$ and $h$ with $a_g+b_g<N$ and $a_h+b_h<N$ and $b_g < b_h$. One member of group $g$ could change to group $h$ and increase the value of $f$ by $b_h-b_g$. This migration can be continued until there is at most one group left with $a_g+b_g<N$. We can also conclude $a_g+b_g<N \Longrightarrow b_g = \min(b_1, \ldots,b_n)$ in an optimal party. Assume $a_g+b_g<N$ and $b_i < b_g$ for any index $i$, then one member of group $i$ could change to group $g$ and increase the value of $f$ by $b_g-b_i$.

If there is a group $g$ with $a_g+b_g<N$ in an optimal party, the elements $a_i$ with $i\neq g$ are all different, because $a_i+b_i=N$ for $i\neq g$ and the $b_i$ are all different. Then we have necessarily an index $i\neq g$ with $a_i=a_g$, otherwise we had a heterogenous partition, in which $a_g+b_g<N$ contradicts optimality.

As mentioned above, the subset of the party, which consists of all groups except group $g$, is a party with heterogeneous partition. All transformations described in the paragraph about optimal parties with heterogeneous partitions never decrease the value of $\min(b_1, \ldots,b_n)$. We can perform these transformations on the subset without creating conflicts with $b_g$, because $b_g$ is already the smallest number of handshakes and will not be met by the results of the transformation of the subset. Following the argument about heterogeneous partitions, we have $(a_1,\ldots, a_{g-1},a_{g+1},\ldots a_n) =(1,2,\ldots , n-1)$ and $(b_1,\ldots, b_{g-1},b_{g+1},\ldots b_n) =(N-1,N-2,\ldots , N-n+1)$ and $b_g=N-n$.

This fully characterizes the optimal parties: Either \begin{eqnarray*} (a_1,\ldots, a_n) &=& (1,2,\ldots , n) \\ (b_1,\ldots, b_n) &=& (N-1,N-2,\ldots , N-n) \end{eqnarray*} or there are $g,i\in \{1,\ldots,n\}$ with $g\neq i$ and $a_g=a_i$ and \begin{eqnarray*} (a_1,\ldots, a_{g-1},a_{g+1},\ldots a_n) &=& (1,2,\ldots, n-1) \\ (b_1,\ldots, b_{g-1},b_{g+1},\ldots b_n) &=& (N-1,\ldots, N-n+1) \\ b_g & = & N-n \end{eqnarray*} In the original problem, we have $N=36$, which leads to $$ (a_1,\ldots, a_8) = (1,2,\ldots , 8) $$ This configuration is also obviously valid in practice, because it means that every participant of the event has to shake hands with each other participant who is not in his/her group. This shows that we have found the optimal solution.


I have an idea what could be the solution, but I have no proof for it, yet. Let us make 8 groups, the first of which contains 1 participant, the second contains 2, the third contains 3 etc. Each guest shakes hands with all of the other guests that are not in his group. Then the member of the first group shakes 35 hands, each member of the second group shakes 34 hands etc. This makes (1/2)*(35+2*34+3*33+4*32+5*31+6*30+7*29+8*28)=546 handshake incidents overall.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.