Noble Knights can shake hands without having to move very much - and without repeats

Posted November 26, 2017

This week, FiveThirtyEight's Riddler featured four puzzles from students. One that really pulled me in was a puzzle about the League of Interesting and Noble Knights (Puzzle 1), which came from the advanced math problem-solving class at Central Academy in Des Moines, Iowa, under the guidance of Mike Marcketti and Brian Reece. Here's the puzzle:

After years of hard work as a devoted tower guard, you have been knighted and are set to become a member of a brand-new group dubbed the League of Interesting and Noble Knights, or LINK. Upon coming to the first meeting, you and the other five members are seated at a round table. There, your boss, King Scott, gives a grand introduction in which he welcomes you all to LINK. The king also outlines a greeting ceremony that must take place at the beginning of every LINK meeting.

• The ceremony concludes when every member of LINK has met every other member with a handshake.
• During each round of handshakes, every member of LINK must be shaking one and only one hand.
• Arms cannot cross during the handshake ceremony as it is in violation of the Universal Law of Respect.
• Between rounds of shaking, the seats can be rearranged.

After this first meeting, King Scott approaches you and asks you to answer the following questions: What is the minimum number of seating arrangements necessary to complete the ceremony for six knights? Eight knights? \(N\) knights?

I had heard a related question before: (2) If you don't worry about seating arrangements and arms crossing, what's the minimum number of rounds you need so that everyone shakes everyone else's hand? Can you be so efficient that everyone shakes everyone elses hand only once (thus using \(N - 1\) rounds)? I had heard this latter question before - the answer is important for scheduling sports leagues where every team plays against every other team exactly once. But I hadn't solved it.

We can combine these two questions into one harder question: (3) Can we design the ceremony so that everyone shakes everyone else's hand exactly once, while also employing the fewest possible number of seating arrangements. The answer is yes, as we'll see below. But what I find particularly cool is that even though (3) is a harder question at face value than (2), the extra contraint of using the fewest number number of seating arrangements focused my search and in the end made the problem easier.

That minimum number of seating arrangements: For 6 or 8 knights, 3 seating arrangements are needed, and more generally \(N\) knights will need \(\lceil \log_2 N \rceil\) seating arrangements.

The lower bound: The knights need at least \(\lceil \log_2 N \rceil\) seating arrangements

The first thing that we will show is that two knights may only shake hands with each other if the distance between them (counting around the circle) is odd. Let's look at one round of handshakes, and pick one of the handshakes to focus on. Since handshakes are not allowed to cross, all knights on one side of this special handshake must be paired off shaking hands with each other, and same with the knights on the other side. In particular, there are an even number of knights on each side of the special handshake. The two knights involved in the special handshake are an odd distance apart, counting around the circle.

If we assign every other knight counting around the circle the color blue, and the rest the color yellow, then blue knights may only shake hands with yellow knights, and yellow knights may only shake hands with blue knights. A knight may not shake hands with another knight in the same color group.

Let \(k\) be the total number of seating arrangments. If we keep track of whether a knight was in the blue group (B) or yellow group (Y) in each of the \(k\) seating arrangments, we get a length-\(k\) "code" of R's and Y's. If two knights had the same code, then they would never shake hands with each other because they would always be in the same color group. So, all \(N\) knights at the meeting have a different code. There are \(2^k\) possible codes, so \(2^k \geq N\). Or rephrased, the number of seating arrangments, \(k\), is at least \(\log_2 N\) (in fact, at least \(\lceil \log_2 N \rceil\) because it must be a whole number).

How to get every yellow knight to shake hands with every blue knight

Knights can only shake hands with knights of the other color, but to get the biggest bang for our buck from a seating arrangement, we'd like every yellow knight to shake hands with every blue knight (exactly once). Here's how to do it. For the one round, the king stands between two of the knights in the circle, and draws a mirror line that goes through himself and the center of the circle. Each knight is the mirror-image of some other knight across tis mirror line. Each knight shakes hands with their mirror.

That means that the two knights adjacent to the king shake hands, the two knights that are two away from the king shake hands, the two knights that are three away from the king shake hands, and so on.

There are \(N\) places the king can stand, but this represents only \(N/2\) possible positions for the mirror. Each of the first \(N/2\) is carried out by putting the mirror in one of these positions. After that, every knight has shaken hands with every knight of the opposite color.

How to carry out the ceremony when the number of knights is a power of 2

In the next two sections, we'll show how to complete the ceremony in \(\lceil \log_2 N \rceil\) seating arrangements, while using only \(N - 1\) rounds (everyone shakes hands with everyone else exactly once). The solution will be recursive; our solution for \(N\) knights will draw upon the solution for fewer knights.

We'll use the case of \(N = 8\) knights as an example. In their first arrangement, we'll color the knights so that they alternate between yellow and blue. Using the procedure from the previous section, every knight shakes hands with every knight of the other color. This takes four rounds.

Then, it's time for the knights to rearrange themselves. First a story. When I was in high school, my friend group wanted to sit together at lunch, but we couldn't fit around one round table. So, we pushed two round tables together like this:

This way we could all sit in one big ring, though it's pinched in at the middle. We mostly ended up talking with the people at the same table, though. When the knights rearrange themselves, we can imagine them sitting around two tables like this. All the yellow knights sit at one table, and all the blue knights at the other. They're technically all in one big ring (which can be pushed back out into a circle as needed), but they'll just interact with the other people at the same table (they've already shaken hands with everyone at the other table). They'll shake hands with one of the people next to them (next to them at their own table, ignoring the people at the other table) in one round:

They'll shake hands with the person on the other side in the following round:

Finally, they each want to shake hands with the person across the table, but they can't do this without crossing hands, so they rearrange themselves one last time before this final round:

That's the solution for 8 knights. But really, it gives us the solution for \(2n\) knights, whenever we already know the solution for \(n\) knights. In the first arrangement, color the \(2n\) knights so that they alternate yellow and blue. Using the strategy from the previous section, have every knight shake hands with every knight of the other color. When the knights rearrange, they'll arrange themselves around my high-school lunch tables, with all the blue knights at one table, and all the yellow knights at the other. Each table (separately) uses the strategy for \(n\) knights to get everyone at the table to shake hands with everyone else at the table.

The solution for \(N = 2\) knights is that they just shake hands in one round. Since we have the solution for 2 knights, by the above we have the solution for 4 knights. And since we have the solution for 4 knights, we have the solution for 8 knights. Continuing on like this, we have a strategy for \(N\) knights whenever \(N\) is a power of 2.

What to do when \(N\) is not a power of 2

When \(N\) is a multiple of 4, and we already have the solution for \(N/2\) knights, then we can construct a solution for \(N\) knights using the strategy from the previous section. But if the number of knights is not a multiple of 4, that doesn't work (in particular, \(N/2\) isn't even), and we'll need a different approach. In this section, we'll show that if we have a solution for \(n\) knights, then we can get a solution for \(2n - 2\) knights.

As before, with the knights in their first arrangement, assign them each a color, alternating yellow and blue as you go around the circle. Have each knight shake hands with each knight of the other color using the system previously described, except, leave out one of the rounds.

Each knight will have exactly one knight of the other color that they haven't shaken hands with yet; we'll refer to this knight as their shadow-partner.

When the knights rearrange, they arrange themselves around my high-school lunch tables, again with all the blue knights at one table, and all the yellow knights at the other. This time, a large mirror is placed between the two factions so that one table is the mirror-image of the other. The yellow knights are careful to always be in the spot that is exactly the mirror-image of their shadow-partner, and do do exactly the mirror-image of what their shadow-partner does. If two blue knights shake hands, their shadow-partners will as well.

The knights make room for one more at their table: a ghost sits right at the point when the two tables connect. Whenever a knight goes to shake hands with the ghost, their shadow-partner goes to shake hands with the ghost as well, and these two knights end up shaking hands with each other instead.

The knights of the blue table, plus the ghost, then all shake hands with each other, using the solution for \(n\) knights (where the ghost stands in for a knight). The yellow knights follow along, always doing the mirror-image of the blue knights.

Here's the second seating arrangement for the example of \(N = 10\) knights:

Third seating arrangement:

Final, seating fourth arrangement:

When they finish carrying out the ceremony for \(n\) knights, they are done with the ceremony for all \(2n - 2\) knights. Then ceremony for \(2n - 2\) knights uses just one more arrangement of knights than the ceremony for \(n\) knights.

By induction, we can now describe a strategy for \(N\) knights for any even number \(N\). We already discussed the strategy for 2 or 4 knights. Since we have a strategy for 4 knights, we have strategies for \(2 \cdot 4 - 2 = 6\) and \(2 \cdot 4 = 8\) knights, using the strategies described in the last two sections. Since we have a strategy for 6 knights, we have strategies for \(2 \cdot 6 - 2 = 10\) and \(2 \cdot 6 = 12\) knights. Since we hae a strategy for 8 knights, we have a strategy for \(2 \cdot 8 - 2 = 14\) and \(2 \cdot 8 = 16\) knights. We can continue onward like this to get a strategy for every even number of knights.