Tuesday, November 29, 2011

this week's MGRE Math Beast Challenge problem

From here:

This Week's Problem: "Friends Of Friends Of Friends"


Joseph has 8 friends. Some of these 8 friends know each other, as follows: Mary knows Dave and Edgar, who also know each other. Edgar, in addition to knowing Mary, knows Lea, Juan, and Greg, none of whom know each other. If Joseph would like to introduce each of his friends to all of his other friends whom that friend does not already know, how many introductions will Joseph have to make?


(A) 2
(B) 10
(C) 22
(D) 28
(E) 58

Good Christ, this looks like one of those permutations/combinations problems. I hate those. My answer will eventually appear in the comments, so stay tuned. Meantime, feel free to offer your own solutions (but please show your work).



Kevin Kim said...

I think the answer is (C), 22. I did this the old-fashioned way, by drawing out the names in a scattered fashion on a piece of paper, and drawing lines to symbolize connections (i.e., people knowing each other). I left Joseph himself out of this scenario because he's the guy who knows everybody, so his only role here is in making the requisite introductions.

There are eight friends, only six of whom are mentioned as knowing each other in some fashion, which means we can assume-- I think-- that the unnamed Friends 7 and 8 know Joseph, but don't know each other and don't know any of the Named Six. Here's the shorthand for the eight friends (again, we're not including Joseph):

M = Mary
D = Dave
E = Edgar
L = Lea
J = Juan
G = Greg
7 = Unnamed Friend #7
8 = Unnamed Friend #8

We draw a triangle, MDE, symbolizing the acquaintance-relationships of Mary, Dave, and Edgar. Radiating out from the Edgar vertex of the triangle, we have three line segments, EL, EJ, and EG, because Edgar knows L, J, and G, but they don't know each other. Sitting off in outer space, unconnected to anybody (remember that we're not figuring Joseph into this), we have Friends 7 and 8-- just two points floating in the blankness.

Next, we draw (and number) all the remaining line segments so that everyone is connected to everyone. When I did this, I ended up drawing 22 such segments, which is why I think (C) is the correct answer.

But here's another way to figure the problem if you're not into messy drawings: using the schema we've drawn, quickly tally up the non-acquaintance relationships. To wit:

M doesn't know 5 people (78LJG)

D doesn't know 5 people (78LJG)

E doesn't know 2 people (78)

L doesn't know 6 people (78MDJG)

J doesn't know 6 people (78MDLG)

G doesn't know 6 people (78MDLJ)

7 doesn't know 7 people (easy to deduce, since s/he knows no one else)

8 doesn't know 7 people (easy to deduce, since s/he knows no one else)

If we total up the "doesn't know X people" tally, we get 44. However, 44 is a double count: if A doesn't know B, then B perforce doesn't know A. That non-acquaintance relationship should count for 1, not 2, in the tally. So: half of 44 is 22, which is, again, why I think (C) is correct.

Horace Jeffery Hodges said...

But the real question is . . . does Joseph truly have eight friends? How can we be sure? And if he doesn't, how can we ever know the number of actual introductions?

In short, I have no reason to trust this math problem, and I refuse to be suckered into answering it!

Jeffery Hodges

* * *

Kevin Kim said...

While I didn't wonder whether Joseph truly has eight friends, I did find myself wondering why he couldn't just gather everyone in a circle and do a single "mass" introduction.