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?
+6248 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\)
