Be my guest...
There are people at a party (n > 2 for finite n) and they can choose to shake a person's hand ( ) or not, but they cannot shake their own hand. Which of the following statements are true:
A) There are at most hand shakes
B) There can be 2n handshakes
C) At least one person, shakes two (or more) hands
D) It is possible for there to be one handshake each
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
A) is not n o t t r u e as handshakes have a 1-1 correspondance to pairs of people, so the most amount of handshakes possible is: ( 2 n ) = ( n − 2 ) ! 2 ! n ! = 2 n ( n − 1 ) = 2 n ( n + 1 ) B) is t r u e as we can have: 2 n ( n − 1 ) = 2 n ⇒ n = 5
C) is t r u e because it is impossible to have someone who shakes everyone's and someone who doesn't shake any hands (I would imagine their encounter would be very awkward). This leaves (n-1) groups, of the number of hands one can shake, which is either (0 - {n-2}) or (1-{n-1}). There are n people, so by the pigeonhole principle one element of either of these groups must contain a least 1 repeated element.
D) is f a l s e from part C. It is important to note that I specified n >2 otherwise n =2 would render D true.