This is our first year competing as a team. Most teams have adult mentors that help them out; we managed to get 25 members for our team with all of zero mentors helping us. Because of that, we got an award at the Awards Ceremony Friday night. No-one on our team really thought we were going to get an award, though, so they all stayed in the pit. Only three people on my team (Morgan, Forrest, and I) went to the ceremony.
So, we ended up getting the Rookie Inspiration Award, which was pretty cool. The three of us went down to claim the award and high-five the judges, and the three of us hugged before receiving the award.
Now, me being the nerd that I am, I got thinking about that today. For three people to hug each other exactly once, you need three hugs. We'll number our people 1, 2, and 3. You need a hug between 1 and 2, a hug between 1 and 3, and a hug between 2 and 3. Makes sense.
In fact, the formula for computing this ends up being 1+2+3+...+n, or (n2+n)/2, where n+1 is the number of people that want to hug.
So, because a single person generally can only hug one other person at the same time (meaning three people can't all hug each other at the exact same time for all intents and purposes concerned here), it takes three units of time, a unit of time being defined as the approximate time it takes two people to hug (which is obviously subjective and depends on how long they hug and other factors I'm not going to account for), for those three people to hug each other exactly once.
So, I started thinking to myself, let's say more people from our team had shown up at the ceremony. Let's say four people had shown up. In order for each of the four people to hug each of the other four people exactly once, 6 hugs need to take place: 1-2, 1-3, 1-4, 2-3, 2-4, and 3-4. Since there are four people, only two hugs can take place over the course of a single unit of time. It would seem likely, then, that all 6 hugs could be completed in three units of time.
So then I thought about how those people would hug depend on where they're standing. Let's imagine them standing in an approximate square, like this (click on the image to view a larger version):
1, 2, 3, and 4 are our people. We have three time periods, each a unit of time long, that we're looking at here: A, B, and C. The dotted lines represent a hug that occurs during that time period. As indicated by the image, during time period A, 1 and 3 hug, and 2 and 4 hug. During time period B, 1 and 2 hug, and 3 and 4 hug. During time period C, 1 and 4 hug, and 2 and 3 hug.
There's just one problem: it's somewhat difficult for 1 and 4 to hug at the same time as 2 and 3 hug without having one of them walk around the other, since they would both be hugging through the center of the image (where the two C lines cross), which obviously wouldn't work. So this arrangement for completing all six hugs isn't going to work.
That seems to necessitate at least some sort of movement on the part of the people involved in order to complete all of the hugs within three units of time. For example, just before time period 3, 2 and 4 could switch places with each other, and then the C lines would parallel the existing B lines and there wouldn't be a conflict. But then the people involved have to remember which time period they're supposed to switch at and who's supposed to switch. What if there was a directed cycle graph involving some of the people that would cause all of the hugs to be carried out in three time periods if the people move one vertex down the directed cycle graph before every time period? That would seem to be simpler.
I set about finding such a directed cycle graph for the four person problem. In less than a minute I had found one that works. Not surprising, really, as there aren't many possible graphs when you only have four vertices.
So, the graph I found is this:
The dotted lines are the hugs that take place, and the arrows form the edges of the directed cycle graph. Three units of time need to elapse for each person to hug each other person, as established before. Between each time period, however, the people that are on the directed cycle graph (which is everyone except 4) move one edge down the graph. So 2 moves to where 3 is, 3 moves to where 1 is, and 1 moves to where 2 is.
So, as shown on the graph, 1 and 2 hug and 3 and 4 hug during the first time period.
Each person then moves down the graph by one position, so that the arrangement of people looks something like this:
Now 3 and 1 hug and 2 and 4 hug. This same process takes place once more, so now the arrangement of people looks like this:
Now 2 and 3 hug and 1 and 4 hug.
So, here's the list of all of the hugs that needed to have taken place in order for all of the people to have hugged each other exactly once:
- 1 and 2 (took place in time period 1)
- 1 and 3 (took place in time period 2)
- 1 and 4 (took place in time period 3)
- 2 and 3 (took place in time period 3)
- 2 and 4 (took place in time period 2)
- 3 and 4 (took place in time period 1)
Before we move on to the problem of six people, I'd like to point out an interesting fact: both the three-person puzzle and the four-person puzzle have the same minimum time period requirement (three) despite the fact that the three-person puzzle only involves three hugs whereas the four-person puzzle involves six hugs. As I'll show either later in this post or in a future post, this is not a coincidence; Every odd-numbered group requires exactly the same number of steps to hug as the next even-numbered group above it, and this stems from the fact that the directed cycle graphs for these end up being almost identical.
Now, on to the six-person version of the puzzle. We'll assume the people are standing in a circle. The vertices representing the people therefore form a hexagon. After a few minutes of trial and error, I found a graph that works for our hexagonal group of people:
As per the formula given above, 15 hugs are necessary in order for all six people to hug exactly once. Since we have six people, three hugs can take place concurrently, so we need a total of 5 units of time to complete all of the hugs. Each of those will obviously have a different arrangement people. Here are the five time periods for the directed cycle graph given above:
Cool, huh.
So I made the mistake of trying to explain this whole puzzle to my mom. It took me quite a bit to explain it to her so that she could understand, and the only comment I could get out of her after that was that I should get some people together and actually try it and then post a video of it on the blog post. If you can't already tell, my mom is quite mathematically disinclined.
Anyway, that's it for tonight. I will, however, mention that graphs for odd numbers look quite a bit different than graphs for even numbers. I'm working on some such graphs in my notebook; I'll post a followup entry with them in a few days.
