+0

0
168
1

22 people attend a party. Each person shakes hands with at most 20 other people. What is the maximum possible number of handshakes, assuming that any two people can shake hands at most once?

Feb 1, 2019

#1
+6045
+3

You can visualize this as an upper triangular matrix where an entry is 1 if element i,j have shaken hands and 0 if not.

If you fill everything above the diagonal with 1's you find that the only row with too many handshakes is the first and only by 1 handshake.

So if we say that person 1 doesn't shake person 22's hand then the rest of the matrix is fine w/regard to your rules.

so we've got

$$n = 20 + 20 + 19 + \dots + 1 = 20 + \dfrac{20\cdot 21}{2} = 230$$

.
Feb 2, 2019