Author 
Message 
peteyip New poster
Post Number: 1
 Posted on Saturday, 08 October, 2011  02:18 pm:  
A finite set P of people meet at a social occasion. some of them shake hands with one another, and no person shakes hands with the same person more than once. Let the set of handshakes S. Let A subset of PxS consist of all pairs (p,s) where the person p takes part in the handshake s. a) show that A is an even number. b) Deduce that the number of people who shake hands an odd number of times is even. not a clue how to start the question, would be very grateful if you helped me 
lebesgue Veteran poster
Post Number: 2381
 Posted on Saturday, 08 October, 2011  03:48 pm:  
Welcome. One handshake contains always two distinct persons, right? 
peteyip New poster
Post Number: 2
 Posted on Saturday, 08 October, 2011  04:15 pm:  
yeah it does, I still dont know how to do about it. :/ Im not the cleverest. 
Emma McCaughan Moderator
Post Number: 4403
 Posted on Saturday, 08 October, 2011  06:10 pm:  
Perhaps, to get a clearer idea of what is going on, the thing to do would be to start with no handshakes, and therefore no pairs (p,s). Then add in some handshakes, one by one, and work out what happens to your subset A. 
peteyip New poster
Post Number: 3
 Posted on Monday, 10 October, 2011  03:00 am:  
im not sure how to show it. At one stage i had 5 people with 5 shakes, which makes A odd, right? 
Emma McCaughan Moderator
Post Number: 4407
 Posted on Monday, 10 October, 2011  08:06 am:  
Go back to Lebesgue's comment: did you have two people in each handshake? 
peteyip New poster
Post Number: 4
 Posted on Monday, 10 October, 2011  01:17 pm:  
lets say we have 5 people (a,b,c,d,e) so if we pair a and b we get (2,1), right? then pair up a and c and we get (3,2) then a and d we get (4,3) then b and c we get (5,4) and so on, is that right? 
lebesgue Veteran poster
Post Number: 2388
 Posted on Monday, 10 October, 2011  01:47 pm:  
You said in your first post that A is a subset of PxS. So let your set of persons be P={a,b,c,d,e}, and set of handshakes be S={s_{1},s_{2},s_{3},s_{4},...}, where s_{1} was the handshake of a with b, s_{2} was the handshake of a with c, s_{3} was the handshake of a with d, s_{4} was the handshake of b with c... So your A consists of the pairs (a,s_{1}),(b,s_{1}) for that first shake, (a,s_{2}),(c,s_{2}) for that second shake,(a,s_{3}),(d,s_{3}) for that third shake,(b,s_{4}),(c,s_{4}) for that forth shake, and so on. 
peteyip New poster
Post Number: 5
 Posted on Monday, 10 October, 2011  01:59 pm:  
thanks,thats really helped erm now part (b), how would i go about starting this? 
lebesgue Veteran poster
Post Number: 2389
 Posted on Monday, 10 October, 2011  02:13 pm:  
So you can see now all those pairs as links drawn from P(persons) to S(shakes), for each s in S there are exactly two links, namely (person_{1},s),(person_{2},s) if person_{1} and person_{2} were shaking in the shake s. So the number of links (when counted on the side of S) is exactly 2S, where S means cardinality of S. But you can compute this number also on the side of P, n(a)+n(b)+n(c)+n(d)+n(e), where n(a) is the number of shakes of person 'a' from P, n(b) is... and so on. What can you tell about parity of these numbers if their sum is even, namely 2S? 
peteyip Poster
Post Number: 6
 Posted on Monday, 10 October, 2011  02:33 pm:  
i havent got a clue :/ 
Emma McCaughan Moderator
Post Number: 4410
 Posted on Monday, 10 October, 2011  05:07 pm:  
I suspect you may not have met terms like cardinality and parity? If you're now happy that A is even, perhaps you should think about the contribution made to A by each person. What would happen to the total if there was exactly one person who shook hands an odd number of times? (This is mostly what lebesgue said, minus some technical terms.) 
