Need help on Sets!! Log Out | Topics | Search Moderators | Register | Edit Profile

 Ask NRICH » Archive 2011-2012 » Higher Dimension » Need help on Sets!! « Previous Next »

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={s1,s2,s3,s4,...}, where s1 was the handshake of a with b, s2 was the handshake of a with c, s3 was the handshake of a with d, s4 was the handshake of b with c... So your A consists of the pairs (a,s1),(b,s1) for that first shake, (a,s2),(c,s2) for that second shake,(a,s3),(d,s3) for that third shake,(b,s4),(c,s4) 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 (person1,s),(person2,s) if person1 and person2 were shaking in the shake s. So the number of links (when counted on the side of S) is exactly 2|S|, 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 2|S|?
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.)