Party shakers...
In any party, there is a lot of handshaking. Show that there are atleast two people who have shaken hands with an equal number of people.
(credits:tuku)
(credits:tuku)
posted by littlecow at 10/07/2005 07:49:00 AM
5 Comments:
I think you need to add the condition that no 2 people shake hands more than once.
when there are 3 ppl A, B, C,
AB => A shook hands with B.
AB, BC, AB => A shook twice, B shook thrice, and C shook once.
I mean the same ppl cannot shake hands more than once in the previous comment.
@erstwhileroomie: the statement is correct as it is. note that the problem reads "two people who have shaken hands with an equal number of people". in your test case, A has shook hands with 1 people, B with 2 and C with 1. hence there exist two people who have shook hands with equal number of people. try again!
Let us consider that n people shake hands in the party.
The least number of people that that they could have shaken hands with such that no two people could have shaken the same number of people are :
1, 2, 3,...., n
Since only n people shaked hands, the maximum number of distinct people that a person could have shaken is n-1. So the above condition is not possible.
QED
@erstwhileroomie, ~a~ : congratulations! you fellows nailed it right. good job!
Post a Comment
<< Home