no. of hand shakes??

[rohit.reddy]

10 people meet and shake hands. The maximum number of handshakes possible if there is to be no "cycle" of handshakes is (A cycle of handshakes is a sequence of k people a1, a2, ......, ak (k > 2) such that the pairs {a1, a2}, {a2, a3}, ......, {ak-1, ak}, {ak, a1} shake hands).
a)6
b)8
c)9
d)7

[goyalsau]

10 people meet and shake hands. The maximum number of handshakes possible if there is to be no "cycle" of handshakes is (A cycle of handshakes is a sequence of k people a1, a2, ......, ak (k > 2) such that the pairs {a1, a2}, {a2, a3}, ......, {ak-1, ak}, {ak, a1} shake hands).
a)6
b)8
c)9
d)7

I am getting 10

[Rahul@gurome]

If there is no cycle of handshakes then a person can shake hand at most one time.
Thus maximum number of handshake = Maximum number of handshake possible by a single person = (0 - 1) = 9

The correct answer is C.

[ssidda01]

If there is no cycle of handshakes then a person can shake hand at most one time.
Thus maximum number of handshake = Maximum number of handshake possible by a single person = (0 - 1) = 9

The correct answer is C.

Hi,

Can someone explain this in more detail. Based on the explaination of what a cycle is, after A1 and A2 shake hands A2 and A3 cannot shake hands next. i.e. A3 and A4 or A3 and A5 or ... A3 and A1 .. can shake hands.

The total combinations of 10 people meeting and shaking hands with other is 10C2 i.e. 45. So now eliminating the cycles from 45 should lead us to our answer.

Please correct where necessary.

Thank you.

[Rahul@gurome]

Hi,

Can someone explain this in more detail. Based on the explaination of what a cycle is, after A1 and A2 shake hands A2 and A3 cannot shake hands next. i.e. A3 and A4 or A3 and A5 or ... A3 and A1 .. can shake hands.

The total combinations of 10 people meeting and shaking hands with other is 10C2 i.e. 45. So now eliminating the cycles from 45 should lead us to our answer.

Please correct where necessary.

Thank you.

If the pairs (a1, a2), (a2, a7) and (a1, a7) has shaken hands then also it is a cycle of handshakes. Note that a1, a2... etc are nothing but representation of the peoples. You can't assign them some numbers and say only if they shake hands in that particular numbered sequence only then there is a cycle of hand shakes. This means if person A shakes hand with person B, and B with some X and X with A again, then there is a cycle of handshakes among A, B and X whatever there representation is.

Let's see why the maximum is 9.
Assume a1 has shaken hand with everybody, i.e. number of handshakes is 9. Now if any of them shakes hand with another, there will be a cycle. For example say (as your example) a3 shakes hand with a4. Remember already there is a handshake of the pair (a1, a3) and (a1, a4). This new handshake of the pair (a3, a4) completes a cycle of handshake among a1, a3 and a4. Same goes for other handshake pairs. Thus maximum number of handshakes cannot exceed 9.

Hope it is clear now.

[ssidda01]

Hi,

Can someone explain this in more detail. Based on the explaination of what a cycle is, after A1 and A2 shake hands A2 and A3 cannot shake hands next. i.e. A3 and A4 or A3 and A5 or ... A3 and A1 .. can shake hands.

The total combinations of 10 people meeting and shaking hands with other is 10C2 i.e. 45. So now eliminating the cycles from 45 should lead us to our answer.

Please correct where necessary.

Thank you.

If the pairs (a1, a2), (a2, a7) and (a1, a7) has shaken hands then also it is a cycle of handshakes. Note that a1, a2... etc are nothing but representation of the peoples. You can't assign them some numbers and say only if they shake hands in that particular numbered sequence only then there is a cycle of hand shakes. This means if person A shakes hand with person B, and B with some X and X with A again, then there is a cycle of handshakes among A, B and X whatever there representation is.

Let's see why the maximum is 9.
Assume a1 has shaken hand with everybody, i.e. number of handshakes is 9. Now if any of them shakes hand with another, there will be a cycle. For example say (as your example) a3 shakes hand with a4. Remember already there is a handshake of the pair (a1, a3) and (a1, a4). This new handshake of the pair (a3, a4) completes a cycle of handshake among a1, a3 and a4. Same goes for other handshake pairs. Thus maximum number of handshakes cannot exceed 9.

Hope it is clear now.

Thank you Rahul.. 'Cycle' is better understood now.

[Salman Ghaffar]

Is this an actual GMAT question?