18. There were 36 participants in a party, some of whom shook hands with each other, such that any two participants shook hands with each other at most once. Each participant then recorded the number of handshakes made, and it was found that no two participants with the same number of handshakes made had shaken hands with each other. Find the maximum total number of handshakes in the party. (When two participants shook hand with each other this will be counted as one handshake.)
(2 marks)
某次聚會共有 36 人參加, 當中有些人曾經互相握手, 而每兩人之間握手最多一次。事後每人均記錄了自己的握手次數, 並發現握手次數相同的人之間均沒有互相握手。求聚會中握手總次數的最大可能值（兩人互相握手時算作一次）。
(2 分)
18. 546
18. For $0 \leq i \leq 35$, let $a_{i}$ be the number of participants who made exactly $i$ handshakes. For a fixed $i$, it is given that the corresponding $a_{i}$ participants did not shake hands with each other. So each of them made at most $36-a_{i}$ handshakes. In other words, we have $a_{i} \leq 36-i$. Thus the total number of handshakes made is
$$
\frac{0 \times a_{0}+1 \times a_{1}+\cdots+35 \times a_{35}}{2}=\frac{\left(a_{35}\right)+\left(a_{35}+a_{34}\right)+\left(a_{35}+a_{34}+a_{33}\right)+\cdots+\left(a_{35}+a_{34}+\cdots+a_{1}\right)}{2} .
$$

There are 35 pairs of parentheses on the right hand side. Since $a_{i} \leq 36-i$ we have $a_{35} \leq 1$, $a_{34} \leq 2$, etc. On the other hand the sum inside each pair of parentheses is bounded above by the total number of participants, i.e. 36. We thus get the following upper bound on the number of handshakes:
$$
\frac{(1)+(1+2)+(1+2+3)+\cdots+(1+2+\cdots+8)+36+36+\cdots+36}{2}
$$

The above expression is equal to $\frac{1+3+6+10+15+21+28+36 \times 28}{2}=546$. This upper bound is indeed attainable, as follows: Partition the 36 participants into 8 groups with $1,2, \ldots, 8$ people respectively. Two participants shook hand with each other if and only if they belong to different groups. Clearly the condition in the question is satisfied and the total number of handshakes in this case is
$$
C_{2}^{36}-C_{2}^{2}-C_{2}^{3}-C_{2}^{4}-\cdots-C_{2}^{8}=630-1-3-6-10-15-21-28=546,
$$
so the answer is 546 .