Last night a friend asked me a fun question about Snapchat:
“Say [our group]] has 26 people in it, but Snapchat has a limit of 16 in a group. How many groups would need to be created so that everyone is in a group with all of the [people in the original group]?”
It was fun to think this one through.
My thought process solving the problem went like this:
First I drew a picture of the people sitting around in a circle and thought about how you might chop them up into groups of 16. The picture below shows two groups of 16 -> one group has the people numbered 1 through 16 and the other has the people numbered from 11 to 26.
At this point I thought that since two groups of 16 had an overlap of 6 people you would need 5 sets of two groups to be sure that all everyone matched with everyone else. The reason, I thought, that you couldn’t do it with fewer was that 4 groups x 6 people = 24 and you needed to get to 26.
But then I realized you could do better than my initial idea of having 5 sets of two groups. My new idea was to make a third group containing the people numbered 1 through 8 and the people numbered 19 through 26. The new cut is shown in the picture below.
After making that group, all I need to do is pair people 9 and 10 with people 17 through 26 and then pair people 17 and 18 with people 1 through 10. That solves the problem with 5 groups.
Yay – with a little thought I’ve cut the number of groups from 10 to 5.
But can you go lower than 5?
My next try looked like this picture:
So, the same two starting groups as before, but now my 3rd group paired people 1 through 6 with people 17 through 26. Now only people 7 through 10 were not paired with everyone and it only required a final group of 14 to pair them with people 17 – 26. Those 4 groups paired all 26 people in the big group with everyone else.
So, great, I’m was now down to 4 groups, but could I get to 3? A little math says no (I think!).
With 26 people you are going to have to make a total of 26*25 / 2 = 325 connections if you want to pair everyone with everyone else. That’s because each person needs 25 connections, but each connection pairs two people (so, I don’t need to connect A to B and then later also connect B to A – that’s why you can divide by 2 in the formula above).
Similarly, each group of 16 will produce 16*15 / 2 = 120 connections. Since 120*3 = 360, maybe there is a way that you can produce the 325 necessary connections with just 3 groups.
However, the overlapping people in the groups are a problem. Two groups of 16 will always contain at least 6 of the same people. Since the connections involving those 6 people are getting double counted (and there are 6*5 / 2 = 15 of them), adding a second group of 16 can’t produce 120*2 = 240 total connections, but rather at most 120 + 120 – 15 = 225 connections. Now, since the 3rd group will have at least 6 overlaps with each of the previous two groups, with 3 groups you can have at most 225 + 120 – 2*15 = 315 connections.
But you need 325 to have everyone connected with everyone, you can’t get there with three groups. So, 4 is the minimum and the method shown starting with the 3rd picture above shows one way to do it with 4. There are probably many others.
Fun little problem 🙂
Mike's Math Page 