We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive pseudonymised information about your use of our website. cookie policy and privacy policy.
 
+0  
 
0
141
1
avatar

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
avatar+5797 
+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

8 Online Users