Problem Solving

monge1980 wrote:There are 10 people in a room. If each person shakes hands with exactly 3 other people, what is the total number of handshakes?

A) 15
B) 30
C) 45
D) 60
E) 120

OA is A) (30/2=15) but I am still confused about this question.

Could you please articulate?

We should think first about the act of the handshake. Let's start with a smaller room of just 4 people A, B, C, and D. We can use the same rules - each person must shake hands with exactly 3 other people (this means that everyone will shake hands with everyone else. If I go down the row, I can count up handshakes by
- pairing with A: AB, AC, AC
- pairing with B: BA, BC, BD
- pairing with C: CA, CB, CD
- pairing with D: DA, DB, DC

That would give 4*3=12 handshakes - but wait! I have over-counted, because BOTH people involved in each handshake are part of my room. So when I pair A with B, I don't want to later pair B with A - its the SAME handshake! Therefore each handshake is getting counted as double - giving credit to BOTH people in the event rather than treating them as a single event. I can re-pair and eliminate the over-count:

- pairing with A: AB, AC, AC
- pairing with B: BC, BD
- pairing with C: CD
- pairing with D: <none left>

So we have 6 pairings, or exactly 1/2 of the 12 we originally counted.

This is why when we have 10 people, we find the total number of hands that reach out for a shake (10 people reach out 3 times each = 30 hands reaching out). But we then have to think of them as pairs in order to create the act of the handshake - so we must divide the number of hands reaching out to shake by 2 since they work together = 30/2 = 15).


Whit

monge1980 wrote:Hi Whit, I tried the same at the beginning, but when I extended to 5 people I didn't get the same rule:

A, B, C, D, E

A: AB, AC, AD
B: BC, BD, BE
C: CD, CE, CA
D: DE, DA, DB
E: EA, EB, EC

Noe eliminate doubleconting ...

A: AB, AC, AD
B: BC, BD, BE
C: CD, CE
D: DE
E: EA

The total now is 10 ... which cannot result from the previous rule

Still doubt on how to approach that...

So here comes the fun with your example - there is actually NO WAY for 5 people in a room to shake hands with exactly 3 people each. Let's look at your original list:

A: AB, AC, AD (This is 3 handshakes for A, and 1 each for B, C, D)

B: BC, BD, BE (But we know that A has shaken hands with B, so B must have shaken hands with A. This means that we have our first problem - according to this list, B has shaken with 4 people - w just didn't list A again)

C: CD, CE, CA (Problem again, you have C shaking hands with D, E and A but according to B's list, C has shaken hands with B as well - we have not counted correctly!)

This is going to continue, so I need to think of a better way to count to see the actual number of possibilities. If I go person by person and assign handshakes, I can see this. Note that all handshakes MUST turn up as duplicates or they can not have occurred. So I will list the handshakes under BOTH people's lists, but put duplicates in parenthesis.

A: AB, AC, AD
B: (AB), BC, BD
C: (AC), (BC), CE (wanted to get E in on the action here)
D: (AD), (BD), DE (can't shake D with C because it isn't in C's list)
E: (CE), (DE)

If there are 5 people, then E will only get to shake hands with 2 people, NOT 3, so the assignment is not possible!

SO - the rule is that the total number of people MUST be evenly divisible by the number of people involved in the action. If the handshake was some strange 3-person handshake, then the total number of people in the room would have to be divisible by 3 in order for everyone to have the same number of events.

Because our handshake is between 2 people, we must have the number of people in the room be divisible by 2 in order for them to each get the same number of handshakes.

So, if there are 20 people shaking hands with 5 people each, then we calculate that as 20*5 (total number of hands shaking) divided by 2 (the number of hands involved in each handshaking event) = 50 (because the number of people, 20, is divisible by the number of people involved in each event, 2 per handshake).

Ah - the fun of weird restrictions!

Whit

monge1980 wrote:Hi Whit, I tried the same at the beginning, but when I extended to 5 people I didn't get the same rule:

A, B, C, D, E

A: AB, AC, AD
B: BC, BD, BE
C: CD, CE, CA
D: DE, DA, DB
E: EA, EB, EC

Noe eliminate doubleconting ...

A: AB, AC, AD
B: BC, BD, BE
C: CD, CE
D: DE
E: EA

The total now is 10 ... which cannot result from the previous rule

Still doubt on how to approach that...

In your example, we can see that A shakes hands with 4 people (when it should be 3). You also have D shaking hands with 4 people.

It's important to note that it's impossible to have each person shake hands with 3 people if there are 5 people altogether (in fact it's impossible if the number of people is odd).

To see why, let's first examine the original question with 10 people.
If we ask each person "How many people did you shake hands with?" the answer will be 3
So if there are 10 people, there are 30 handshakes (10x3=30)
However, this calculation counts each handshake twice, so we need to divide 30 by 2 to get 15.

If we attempt to use the same approach for 5 people, we first get a total of 15 handshakes (5x3=15), but to account for the duplication, we must divide 15 by 2 to get 7.5 handshakes, which cannot be true.

Cheers,
Brent

monge1980 wrote:I like this visual approach, but I am wondering whether the rule 30/2=15 ca be extended to all the cases or it is only a coincidence. What is the generalized rule?

Maybe we can follow only a visual approach...

It CAN be applied in ALL cases where the division of handshakes is possible (see full notes above). If the number of total people is divisible by the number of people in each event then I find the total and divide by the people per event.

So in this example, I need the total number of people in the room to be divisible by the number of people sharing a handshake - so the total must be divisible by 2. The reason - if it is not divisible, then we cannot have everyone perform the same number of events (be it 1 handshake or 20 handshakes each). Think about the scenario of 9 people in a room - now ask them to shake hands with exactly 1 person each. They can't! Why - because when I pair them up, poor person #9 gets left all alone!! Same goes with asking for 2 handshakes each, or 3 handshakes each, etc.

To make this a bit more clear - pretend that the act of shaking 3 people's hands each goes like this. A whistle blows and everyone has to pair off and shake their first hand. If the total number of people is not evenly divisible into pairs, then someone misses a handshake. A whistle blows again and everyone has to pair with someone new. Again, someone is going to have to be left out! The 3rd whistle blows and it happens all over - someone has to get left out of a handshake. This is why it is NOT POSSIBLE to make a group of 5 people pair off the same number of times!


Whit

monge1980 wrote:Exactly Whit, I was struggling to get the rule and actually you are right

How do you think I can drill down this matter? Do you have some good source in mind?

Thanks

Hi monge1980!

So the first thing I would say is that this is a fairly esoteric rule with VERY short range impacts. What does this mean for your studies - its not worth researching or committing to memory! Why, when it is FAR more likely that you will NOT see a question like this than that you will!

But that does not mean that playing with these patterns should be ignored. What I would suggest as more important is an investigation in patterns. I tell my students this a lot:

It is far less important that you go through all of the Number Properties and memorize the patterns, but absolutely imperative that you understand that patterns exist.

What do I mean?

Well just this - the GMAT is never going to give you a problem where the only solution is to list or compute 10s or 100s of numbers/combinations in order to solve. There will always be a "trick"! BUT, its nearly impossible to go our and learn/memorize every potential number pattern in the universe!! That would be nuts. Instead, when you see a problem like this, tell yourself - "I know there is a pattern here, can I think about it?" Maybe you'll want to write out the first couple of example numbers or combinations so that you can start to actually see the pattern. Maybe you will simply need to "think" about it and make a logical deduction.

For example, in krk's first approach:

Krk wrote: Approach 1:
If all 10 people shake hands to 3 other people, then 30 handshakes will be there.
In order to avoid the repetition, the number of handshakes should be less than 30.
The only answer less than 30 is 15.
So i will go for that.

This is absolutely elegant! Sure, its not terribly scientific, but it gets the job done, and Krk recognized a pattern - I know the total number but I also know that it is over-counting! Taken one step further, we could surmise that in each handshake, 2 agents are present, so while each individual sees this as their own handshake - it is actually ONE event. Therefore I actually KNOW my over-count.

But now you might ask - but what if they had told me that there were 9 people and they were to shake hands with 3 people each - what would I do because that is an exception to the logic??? Well, guess what - they CAN'T give you that example because it cannot be done! They cannot ask you for the answer to an impossible question!!

So relax, learn to recognize where there is likely a pattern, and be willing to poke at a problem to make it "show" you its pattern. No sense going nuts with flash cards trying to cover every possible number pattern in the universe. If you managed to memorize them all, you were WAAAAAY too smart to be studying for this test in the first place! Heck, I'd like you to Tutor for my PhD!! ;-P

Good Luck!!

Whit