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!!

Rules of Enragement

During a discussion over the merits of Obama’s presidency the other night, my correspondent heatedly insisted that the military hates Obama and that a major reason for this is the changes he’s made to the Rules of Engagement or ROE, which spell out when and how US military forces may “engage with” (i.e. open fire on) enemy forces. It was my friend’s opinion that under Obama, these have become more restrictive, in essence allowing the enemy (e.g. Taliban or ISIL combatants) greater latitude before US forces could deem returning fire justified.I researched the broader (the military hates Obama) claim, and this specific (ROE) claim and I would like to point out the following:

First of all, despite how much control you might think a president has, he (or she) doesn’t usually have any direct say in such details as ROE. That’s what generals and diplomats are paid to do. In the region in question, it was McCrystal and, later, Patraeus who developed those, based on their knowledge of counter insurgency and the intricate political and military workings of the region. Obama’s role in this amounts to, perhaps, hearing briefs on them, but, probably not much more than signing off on them.

Secondly, as of January of this year, the ROE have actually become LESS restrictive. For example, whereas before US troops had to actually see hostile intent (someone had to shoot at them before they could return fire, say), current ROE in Afghanistan allow them to fire on someone who’s doing nothing more than wearing an ISIL T-shirt.
What’s telling, however, is that in spite of this change, nearly all of the sites that come up when you do search for “Obama” and “ROE” are historically right-wing mouthpieces (e.g. Washington Times, Fox News, Breitbart, &c), repeating the clearly specious claim that Obama has made things more dangerous for our troops. What they conveniently omit is that Generals McCrystal and Patraeus both had more restrictive ROE, which they based on the their experience that showed counter-insurgency or COIN operations don’t use the same calculus as all-out combat. Expending huge resources to kill just a few of the enemy makes you look weak in their eyes. And even if you take out many of them, because these are “locals”, the more you kill, the less support you have among the population and, consequently, the better it is for your enemy. Sometimes, you “win” more (or lose less) by not fighting. At least not directly.

In fact, Obama ordered more drone strikes during his first month in office than did GWB during his entire presidency. That is to say that, rather than send troops into harms way, Obama has opted to use alternative methods. You may question (as I do) the morality of doing that on other grounds, certainly. But, in terms of trying to limit troops exposure to danger, I think Obama has done a better job than he’s being given credit for.

This brings me to the broader claim that the troops hate Obama. While “hate” is a rather strong word, it seems that Obama does indeed enjoy the lowest approval ratings. among the military, of any president in recent memory. But, on closer examination, this has nothing to do with ROE or anything about soldiering or military strategy. It has more to do with career choice, gays, and the role (and treatment) of women in the military.

According to a recent survey conducted by the Military Times, The main gripe you hear from those service persons who voice disapproval of President Obama is that their career opportunities and benefits — promotions, pay increases, posting preferences, &c — aren’t coming as often or as easily as they once did. One article even used the term “military EMPLOYMENT” (as opposed to military service) when describing the elevated levels of dissatisfaction. In other words, this is about job dissatisfaction, rather than matters of foreign policy, rules of engagement, or the price of tea in Mosul.
The other gripe is about the change in the military policy toward gays. And, as it happens, there’s a pretty clear divide in terms of who cares and who doesn’t. Most of the grumbling on this point comes from those who have been in the military the longest. You don’t hear it so much from newer, younger men and women. And, when pressed, regardless of career longevity, most if not all will tell you that it has made little or no difference to those who aren’t gay.

Coincident with this is the lifting of restrictions on women in combat roles. Women can now fly combat missions in fighter aircraft, and participate in combat on the ground. Those who object say that it distracts the men who, they claim, will “instinctively” try to protect the women first. Most, however, quickly point out that women have always been in combat zones: this is just a different way to be in those zones.

Lastly, and perhaps most significantly, is the reaction to Obama’s crackdown on sexual assault in the military.   Obama has instituted a very strict, zero-tolerance approach to this and the “old boys” don’t like it one bit.  Their claim is that it has made their work environment uncomfortable, that the flow of communication among co-workers is hampered by the sense that saying the wrong thing will land you in hot water more easily now.   Try as I might (and I have to admit, I’m not trying all that hard) I just can’t feel alot of sympathy for their “discomfort”.   Incidents of rape and sexual misconduct have, for too long, gone unreported or the accuser has wound up being assaulted by their rapist and then by the military justice system seeking to make the matter go away without holding anyone accountable.   That has changed and continues to change and it comes as no surprise that the ol’ boys don’t like the new rules  one bit.  Small wonder they hate the guy who has spoiled their fun and their “workplace camaraderie”.

The military has changed a great deal over the past two or three decades, both in terms of its mission and composition. Some of the larger changes have come during if not as a direct result of Obama’s administration.   Change is never comfortable and anyone who has been a part of any large organisation undergoing major changes knows these are always accompanied by much grumbling and dissatisfaction among those who preferred the “old ways” of doing things, who want things to remain the way they “always were”.   The same hold true for the military.   Their disapproval of Obama can generally, if not entirely be summarised as resistance to change.   Blaming Obama for changes in ROE, or saying the troops hate him for being a “bad CIC” are simply unsupportable by fact. This of course doesn’t stop right-wing pundits, repeating lies big and small,  as often often as it takes until they are accepted as truth.

References: