A problem worthy of attack: Friend groups

Quick post to share a really interesting problem a student of mine (G.) posed the other day.

Here’s the context: Last week, our school held a Box Lunch Auction, which involved homerooms preparing lunches of various sizes (e.g., for 6 people, for 10 people, for 30 people) and groups of students bidding on said lunches. The money raised was donated to various local charities.

Reflecting on the experience, G. wondered if the sizes of the lunches might be determined in a way that better suited the needs of the student body, rather than more or less randomly (truthfully, based on how much work a homeroom was prepared to do). This is the question he posed:

Let’s imagine that any two people in the school have a 50% chance of being friends. With n people, what’s the most likely size friend group?

I was hooked immediately.

To start, we lay down some assumptions. In particular, we assumed that if, for example, A and B were friends, and B and C were friends, then A, B, and C formed a friend group. In other words, in a friend group, everyone has at least one friend in the group, and all groups are disjoint (a student only belongs to one friend group). Then, I suggested that n students was a bigger problem than we could handle at the moment, and that we should simplify it to start, at least to get to know the problem a bit before trying to generalize. So, we asked: What if there were just 3 friends?

We drew a diagram:

Here’s what we found for this particular case (spoiler alert!):

If all friend groups are size 1, no students are friends with each other. The probability of this occurring is (0.5)(0.5)(0.5) = 0.125 (i.e., A and C aren’t friends, A and B aren’t friends, and B and C aren’t friends). Groups of size 1 may also occur when two students are friends with each other, but not with a third student. The possibilities are A and B being friends, B and C being friends, and A and C being friends, with the remaining student not friends with either. For the first case, A and B are friends and C isn’t friends with either A or B, which has a probability of (0.5)(0.5)(0.5). The total probability of groups of size 1, then, is (0.5)(0.5)(0.5) [none of the students are friends] + (0.5)(0.5)(0.5) [only A and B are friends] + (0.5)(0.5)(0.5) [only A and C are friends] + (0.5)(0.5)(0.5) [only B and C are friends] = 0.5. The probability of a size 2 friend group is the same as the latter three cases: (0.5)(0.5)(0.5) [only A and B are friends] + (0.5)(0.5)(0.5) [only A and C are friends] + (0.5)(0.5)(0.5) [only B and C are friends] = 0.375. Finally, the probability of a size 3 friend group is 4(0.5)(0.5)(0.5) = 0.5 (this includes the situation that all students are friends, or that, e.g., A and B are friends and B and C are friends, but B and C are not friends). (These probabilities do not sum to 1 because the probability of groups of size 1 includes the possibility of a group of size 2.) So, it turns out that size 3 friend groups and size 1 friend groups are the most likely to occur.

Interestingly, the probability that you (e.g., Student A) will end up in a size 1 friend group (i.e., with no friends!) is not 0.5. This will occur only if you are not friends with B or C, which has probability P = (0.5)(0.5) = 0.25. The probability that you end up in a size 2 friend group is equally likely: P = (0.5)(0.5)(0.5) + (0.5)(0.5)(0.5) = 0.25 (either you are friends with B and C is friends with neither you or B, or you are friends with C and B is neither friends with you or C). Finally, the probability that you end up in a size 3 friend group is P = 4(0.5)(0.5)(0.5) = 0.5, which occurs either when there are exactly two unique friend pairs (e.g., you are friends with B and B is friends with C) or when all pairs are friends with each other. From this perspective, you are pretty unlikely to end up with no friends – more likely, you will end up in a group of 2 or 3 friends. (I’m now imagining this as part of the “Welcome to high school!” presentation to Grade 9 students that’s meant to calm their nerves. I have a feeling it wouldn’t help…)

What happens when we add more students to the school? Is it always true that the largest possible friend group is the most likely? Initially, G. and I drew the following diagram and tried to do a similar analysis:

But soon, we realized that it was incomplete (can you see why?). The problem seems to get very complex quite quickly (what if there were 8 students? 100? 1000?), so we may have to get a bit more creative in our approach when we come back to it next week.

I love this problem, which is proving to be much deeper than initially expected. (But, after all: “Problems worthy of attack prove their worth by fighting back.”) I love even more that a student posed it. If you have any suggestions for a good strategy of attack, or if you recognize this as analogous to a similar problem, let me know. I’m looking forward to seeing where this one takes us.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s