\section*{Problem 10 - V01210}

At a New Year's Eve party, where 300 people are present, everyone congratulates each other with a handshake at midnight.

How much time does this take if all persons start congratulating simultaneously and each handshake takes 3 seconds?

Solve the problem generally and then with the values given in the text.
}

Let there be \(n\) people present. Since everyone congratulates everyone else, the number of congratulations corresponds to the number \(z\) of ways to choose exactly 2 out of the \(n\) people, i.e., \(z=\binom{n}{2}=\frac{n(n-1)}{2}\).

If \(n\) is even and the people congratulate each other simultaneously, \(\frac{n}{2}\) pairs can shake hands at the same time. Therefore, \(n-1\) rounds of congratulations are required, which take \(3n-3\) seconds.

If \(n\) is odd, \(\frac{n-1}{2}\) pairs can shake hands at the same time, while one person always has to wait. Therefore, \(n\) rounds of congratulations are required, each taking 3 seconds.

"Congratulation Plan":

Number the people with \(1, \ldots, n\).

1. Case: Assume the number \(n\) of people is odd.

Then consider the following congratulation plan:

For \(r=1,2, \ldots, n\), in round \(r\), the person with number \(i\) should congratulate the uniquely determined person with number \(j\) for which \(i+j \equiv r(\bmod n)\) holds. If \(i=j\), then person \(i\) sits out in this round.

Correctness Proof:

Since \(i+j=j+i\), it is clear that in each round, the person \(j\) who is supposed to congratulate person \(i\) according to the plan will also congratulate person \(i\). Thus, the planned congratulations are always possible.

Moreover, each person congratulates every other person exactly once: The persons \(i, j\) congratulate each other in the round \(r\) for which \(r \equiv i+j(\bmod n)\) holds.

Observation: Since \(n\) is odd, there is exactly one person \(i\) in each round \(r\) who sits out, i.e., for whom \(2i \equiv r(\bmod n)\) holds. Furthermore, for each person, there is exactly one round in which the person sits out.

2. Case: Assume the number \(n\) of people is even.

Consider person \(n\) separately from the others. The new plan is to execute the plan for persons \(1,2, \ldots, n-1\) according to Case 1, with the difference that the person who should sit out congratulates person \(n\).

Formally: For \(r=1,2, \ldots, n-1\), in round \(r\), the person \(i\) (with \(1 \leq i < n\)) should congratulate the person \(j\) with \(i+j \equiv r\) (mod \(n-1)\) (if \(j \neq i\)) or the person \(n\) (if \(j=i\)).

The correctness follows from Case 1 and the above observation.

For the specific case \(n=300\), \(z=\binom{300}{2}=44850\). The 299 rounds of congratulations require 897 seconds, i.e., \(14 \text{~min} 57 \text{~s}\).