The optimal location algorithm

Question

There are twenty five chairs in a row. Clients that enter the panel follow these two rules:

• The client will always sit in the place farthest from any other client.
• The client will never sit next to another client.

Using these two rules, where should you place the first client so that the maximum number of clients can sit on the panel?

I can solve this in 25 conditions of the chair. But I can not find a general algorithm for the n chair.

Answer 1

The sound is almost the same as the “International Urinal Choice Protocol” (ICUP), which Randall Munro wrote an excellent analysis, including a closed-loop equation and a graph of the optimal number of urinals. You should read his article before reading the rest of this answer.

---

In a post, Randall mentions:

[I] If you enter the bathroom with an uncomfortable amount of free urinals in a row, instead of taking one of them, you can walk one third from the line down. This will break the inconvenient line into two optimal lines, turning the worst case scenario into the best case.

Until he delves into more detail, he hints at what we are trying to do. If we have an uncomfortable amount of urinals (or stools in our case), we can try to put the first person in place so that they become the end of two different optimal subgroups.

Within 7 places, the main selection mode sets this:

1 _ _ 3 _ _ 2 

Leaving four unoccupied places. But if instead we place the first person in third place, we will get the optimal 3 and 5 subgroups, increasing the number of possible passengers by one.

 3 _ 1 _ 4 _ 2 

For 25, the basic behavior is similarly non-optimal, which leads to the 9/25th filling before awkwardness:

 1 _ _ 6 _ _ 4 _ _ 7 _ _ 3 _ _ 8 _ _ 5 _ _ 9 _ _ 2 

But we can put someone in position 9, creating optimal 9 17 subgroups, for example:

 3 _ 8 _ 5 _ 9 _ 1 _ 10 _ 6 _ 11 _ 4 _ 12 _ 7 _ 13 _ 2 

Ensuring optimal employment 13/25th.

More generally, I believe that finding the largest optimal number is less than the number of places, and placing the first person there (in 25 cases 17, which is equivalent to the 9th from a different direction) will always maximize the number. In the worst case, for example 25, this is equivalent to ceil(n/3) , which Randall mentions.

In the middle case (neither the best nor the worst use of the basic seating behavior) we can always achieve 50% employment only by sitting in front of the first person, because we can create only one optimal subgroup, leaving the other less optimal. Therefore, we take the largest optimal subgroup in order to minimize the number of suboptimal spots. For example, for 20 places, we take 17 and create a group of 17 4, which optimizes as many places as possible, leaving only two lines empty:

 2 _ 7 _ 4 _ 8 _ 3 _ 9 _ 5 _ 10 _ 1 _ _ 6 

The four groups are actually technically the best and worst, but hopefully you can see how the template will scale.

Answer 2

Here is my analysis.

For the argument, let's say the first person sits somewhere in the middle, not too close to the end. This will give us a picture where x denotes the occupied space and free space:

 _ _ _ ... _ x _ ... _ _ _ 

The first client sitting to the left of this person will be sitting at the left end. Similarly, the first customer sitting to the right of this person will be sitting in the far right corner. This leaves us with a pattern where -m- stands for m consecutive free spaces:

 x _ -m- _ x _ -n- _ x 

Call this "basic configuration" the total number of places s = m + n + 7.

So, now our problem is divided into two subtasks of size m and n, each of which will be filled by a client sitting as close to the middle of each area as possible.

For maximum final employment, we want m and n to be “ideal” numbers, defined as follows:

 a is ideal if a = 2b + 3 and b is ideal (ie, we will get -b- _ x _ -b-). 

The idea here is that the ideal number of places can be maximally occupied (1), taking the middle place a and (2), a recursive solution for two sub-problems of size b.

The least ideal number is 1.

From this, you can build the first few ideal numbers:

 1, 5, 13, 29, ... 

Now, for s = 25, our basic configuration says 25 = m + n + 7 and we want m and n to be perfect. Well, 25 - 7 = 18 and 18 = 5 + 13, which are perfect!

Thus, for 25 seats we sit the first person in the seat 4 + 5 = 9 or 4 + 13 = 17, and we are guaranteed to finish the maximum employment.

The last thing to check before we finish: what if the first client was sitting on the end of the chair? Then, after the second client sits, we will have

 x _ -m- _ x 

where m must be an ideal number. For 25 places this gives 25 - 4 = m = 21, which is not ideal. Therefore, the first client cannot sit at both ends in order to maximize the use of 25 seats.

Ta daaaaaah!

Answer 3

When you actually draw a picture, you will find that the answer will be very simple. For example, in the following cases, you can easily choose places on the left, right, or in the middle.

Eg1 OOO --- XOX - 1

Eg2 OOOOO - XOOOX - XOXOX - decomposes from 3 to 1

For example, OOOOOOOOO - XOOOOOOOX - XOOOXOOOX - XOXOXOXOX - decomposes from 7 to 3 to 1.

From these examples, we can make the following statements: Assuming that we have a range of free places between two selected places, when the number of free places is N = 2 ^ n-1, we can get the maximum selection of places in this range.

Evidence:

• base case: when n = 1, N = 1, that XOX satisfies the requirements.
• Assuming that this is true when n <= k (with k> 1), which means that when the number of free spaces between two selected places is N = 2 ^ k-1, we can achieve the maximum choice. For the case k + 1, we have N = 2 ^ (k + 1) -1. Then we can choose the middle saddle in this range, making free space for 2 segments, each with the number N '= (N-1) / 2 = (2 ^ (k + 1) -1-1) / 2 = 2 ^ k -1, which is true from our assumption.

So, the algorithm for this problem:

Given the number of places N, we find the largest number 2 ^ n-1 <N-3, then check if N-1- (2 ^ n-1) -1-1 in the form 2 ^ m-1.

In the case of N = 25, one can find that 15 is the largest number below 25 and in the form 2 ^ 4-1. Since 25-1-15-1-1 = 7 witch has the form 2 ^ 3-1. Thus, 25 seats can achieve maximum selection. And according to our analysis, we can choose the first place in 17 or 9.