Anti-social Drinker Puzzler

A friend of mine recently had an interview for a software position, and was given the following problem...

There is a bar with 25 equally spaced stools. The patrons are anti-social and will always choose the stool that maximizes the minimum distance to other patrons. And, no patron will choose to sit next to another. If there isn't any spot that is insulated from others, then no more patrons can be seated. As the owner, you get to seat the first patron, but after that initial placement, the new patrons will seat themselves according to the aforementioned rules. Where do you seat the first person to maximize the number of customers?

So, I thought about this a little bit, and decided that the more general related problem was maybe a bit more interesting. Here's a slightly different question that is a bit more general. Given a bar with N stools, is it possible to seat (N + 1)/2 patrons? I came up with a solution, but it's not really all that elegant, but I do believe it works.

I'm going to skip a ton of the details, but what I came up with is the following. Let's start with what I am going to call a safe interior median partition (SIMP). These are interior stool groupings where splitting down the middle creates two SIMPs. Safe, meaning odd numbered. This is because as soon as we see even numbers, we know we can't fill it up to full capacity.

Not all interior median partitions are safe. Say we had the following: O O O O O O O. We care about the interior, so let's put patrons on the edges. Now, we have: X O O O O O X. Now, we have an IMP of size 5 (there are 5 stools on the interior). This is not safe since it leads to even-numbered IMPs. If we put a patron in the center, we'd have X O O X O O X, and that's clearly not what we want. We can't achieve full capacity using a 'sit in the middle' strategy. So, we know that IMP-5 is not a SIMP.

Now, if we had O O O O O O O O O. We block the edges, giving us: X O O O O O O O X, and we see that this gives us an IMP of size 7. But, look at what happens when we put a person in the middle. We then have X O O O X O O O X. And, we now have two new IMPs, each of size 3. Notice that the IMP of size 3 allows us futher partitioning with a central-seating. Giving us X O X O X O X O X. So, we know that IMP-3 is a SIMP, and IMP-7 is a SIMP, as it produces two IMP-3's.

We have a SIMP, if we have an IMP-X where X is of the form (2^N - 1). So, we can generate our list of SIMPs: 1, 3, 7, 15, 31, 63, etc.

Now, how does this help us? Basically, here's the deal. If we have N barstools, then I contend that we can fill it to capacity, which means (N + 1)/2 patrons seated according to the rules, if and only if we are able to find two SIMPs that sum to (N-3). Once we find our two SIMPs, then simply take one of them and add 2 to find the initial seating. Since we are choosing a first seat to give us two SIMPs, we are guaranteed to fill to capacity, because each median seating produces new SIMPs.

Here are a few examples with illustrative seatings:

N = 25. (N-3) = 22. Our two SIMPs are 7 and 15, which sum to 22. So, we choose initial seat 9.

N = 19. (N-3) = 16. Our two SIMPs are 1 and 15. We choose initial seat 3.

N = 13. (N-3) = 10. Our two SIMPs are 3 and 7. We choose initial seat 5.

N = 15. (N-3) = 12. There aren't two SIMPs that sum to 12. So, there does not exist an initial seating that gives us full capacity. You can see this is the case below, as I've exhausted the possibilities (ignoring symmetric cases).

Click Image to Enlarge

And, that's really all there is to it. If you can find two SIMPs that sum to N-3, then you can certainly fill to capacity. Otherwise, you are bound to have some two-seat gaps in the final seating configuration.