Babette’s Feast

This is a fun little puzzle inspired by the movie Babette’s Feast and my solution provided me with an opportunity to learn how to use the MathTex plugin for WordPress to render mathematical expressions.

The Problem:

For her feast, Babette invited many people to be seated around a round table. She prepared a table plan but all the guests arrived and took a seat so that everyone was sitting in front of somebody else’s place. Is it possible to turn the table so that at least 2 guests are sitting in the right place?

The Solution:

The short answer is, Yes, it is possible. Another way to phrase this is to ask, Does there exist an arrangement of guests around the table such that prior to rotating the table, no guest is found at his or her assigned seat, and following a rotation of the table (guests remaining where they are) at least 2 guests are at their assigned seat? Consider two specific cases. (Note that the number of guests is always the same as the number of assigned seats. For simplicity, we’ll assume the table is round, and we’ll also assume that both the guests and the seating are equally distributed around the table so the space between any two seats is the same for all seats around the table.)

Case 1: Just two guests, each initially at each other’s assigned place, π radians apart. Rotate the table through π radians and both guests are now seated at their assigned seats. (Somewhat trivial, and yet it looks like it might be a nice base case for a proof by induction.)

Case 2: More than two guests, each seated one place to the left of their assigned seat. Rotate the table clockwise one place and every guest is now seated at their assigned seat.

But, the problem is harder than that, isn’t it? We want to know if, for ANY given seating arrangement and distribution of guests where no guest is at his or her assigned seat, if it is possible to rotate the table to where at least 2 guests are now at their assigned place.

Let’s define the distance d_{gp}  between a guest g_i  and his/her place p_i  be the minimum number of places to the left or to the right the table would need to rotate for that guest to find themselves in front of their assigned place. Note that  d_{gp}  is never more than \frac{n}{2}  where  n is the number of guests.

If every guest were maximally distant from their place, the sum of these distances would be bounded above by n\left( \frac{n}{2} \right)  or \frac{n^2}{2} .  The actual sum of the distances is given by

\displaystyle\sum_{i=1}^n \frac{n^2}{{|g_i - p_i|}} \leq \frac{n^2}{2}

Rearranging this a bit gives us

 2\leq\frac{1}{\sum_{i=1}^n \frac{1}{{|g_i - p_i|}}

Notice two things: First, this is only defined if there is at least one misalignment. Since we’re not interested in the fully-aligned case this isn’t a problem. The second, and more important thing to notice is that the minimum actual distance will never be less than 2. This makes intuitive sense if you look at case 1, above. But, consider yet another case where n > 2 and all of the guests are in their proper seats. The minimum misalignment possible is achieved by picking any two guests seated next to each other and having them swap seats. The distance between all other guests and their respective places will be zero, but for each of these two guests it will be 1. 2 x 1 = 2, i.e. our lower bound. Since the left-hand side is a constant, this holds for all n > 1.

Keeping this same arrangement in mind, observe that no matter how many times we rotate the table, in either direction, we cannot return these two to their original (i.e. correct) places. We can misalign all of the other guests by rotating just one seat to the left or to the right, leaving at least one of the two misalligned seats still misaligned. To put this another way, we have constructed two subsets of seats – the misaligned subset, and its complement, the aligned subset. Moreover, there can never be just one misaligned pair; there must always be two.

Now, consider the two sequences {g} and {s} which represent arbitrary but otherwise fixed orderings of our guests and their seats. Suppose the first element of {g}, g_i  aligns with the first element of {s}, s_i . If we examine the rest of {g} vs {s} we’ll either find a match … or we won’t. If we find another match, we have our two guests seated at their assigned places and we can start the first round of aperitifs.

But, if the first elements do not match, the drinks must wait. We rotate {s} so that s_{i+1}  becomes s_i , for i in [1,n], moving s_1  to s_n . We apply multiple rotations until an s_1  aligns with g_1 , and look for a second matching pair. Again, if we find a second matching set, we’re done. Drinks are on. If there isn’t a match (put the decanter down, colonel) we still have more work to do. Rotate {s} again until s_2  aligns with g_2  and look again. But, notice that our search space has shrunk by 1. We can continue doing this all the way down until we are looking at g_{n-1}  matching an s_{n-1}  (after some number of rotations) and a g_n  that must match s_n . Why must it? Recall that even in the most minimal misalignment of guests vs seats, there will be at least TWO mismatches. Consequently, by rotating through all of the matches, then mismatching them by rotating, we are isolating those mismatches. And these aren’t just any mismatches. These are mismatches that are NOT swaps. In fact, they are in the complement of the set of mismatches resulting from swaps, making them mismatches by rotation. Since all we have done is rotate the elements within {g} and {s}, and not change their order, we have accomplished what we set out to do: we have rotated the seats (i.e. places), keeping the guests stationary, until at least two of the guests find themselves at their assigned place.

Now then, Let’s EAT!!

Leave a Reply

Your email address will not be published. Required fields are marked *