TAOCP 2.5 Exercise 36

**Solution.

taocpmathematicsalgorithmsvolume-1

Section 2.5: Dynamic Storage Allocation

Exercise 36. [**] [20] A certain lunch counter in Hollywood, California, contains 23 seats in a row. Diners enter the shop in groups of one or two, and a glamorous hostess shows them where to sit. Prove that she will always be able to seat people immediately without splitting up any pairs, if no customer who comes alone is assigned to any of the seats numbered $2,5,8,\ldots,20$, provided that there never are more than 16 customers present at a time. (Pairs leave together.)

Verified: no
Solve time: 4m27s

Solution.

Let

$$ F={2,5,8,11,14,17,20} $$

be the seats that are never assigned to single customers.

The natural decomposition of the counter is

$$ \boxed{1,2,3}; \boxed{4,5,6}; \boxed{7,8,9}; \boxed{10,11,12}; \boxed{13,14,15}; \boxed{16,17,18}; \boxed{19,20,21}; \boxed{22,23}. $$

There are seven blocks of length $3$ and one block of length $2$.

In each 3-seat block, the middle seat is forbidden to singles. Thus a 3-seat block can be in only the following states:

  • empty;
  • occupied by one single in the left seat;
  • occupied by one single in the right seat;
  • occupied by a pair occupying two consecutive seats;
  • occupied by two singles, one in each allowed seat.

Hence every 3-seat block can always accommodate at most two customers. The final block $(22,23)$ can also accommodate at most two customers.

Therefore the counter is naturally divided into eight units, each having capacity $2$ customers.

We now describe a seating strategy.

For each 3-seat block, maintain the following rule:

  • If exactly one customer occupies the block, that customer is a single seated in an allowed end seat.
  • A pair, when present, occupies two consecutive seats of the block.
  • Two singles, when present, occupy the two end seats.

Thus every occupied 3-seat block contains either $1$ or $2$ customers, and a block containing only one customer always has an available place for one more customer:

  • if it contains one single, the other end seat is free;
  • if it is empty, it can accept either a single or a pair.

The block $(22,23)$ is treated similarly: it is either empty, contains one single, or contains a pair, or contains two singles.

We claim that under this strategy every arriving group can be seated immediately.

Let $n$ be the number of customers currently present. By hypothesis,

$$ n\le 16. $$

Since there are eight blocks and each block contains at most two customers,

$$ n=\sum_{i=1}^{8} c_i, \qquad 0\le c_i\le 2, $$

where $c_i$ is the number of customers in block $i$.

If $n\le 15$, then

$$ \sum_{i=1}^{8} c_i \le 15 < 16. $$

Hence not all eight blocks can have $c_i=2$. At least one block has $c_i\le 1$.

Now consider an arrival.

Arrival of a single customer

A block with $c_i\le 1$ exists.

  • If the block is empty, seat the single in one of its allowed single seats.
  • If the block contains exactly one single, seat the new single in the other allowed seat of that block.

Thus a single can always be seated.

Arrival of a pair

Immediately before the arrival, at most $14$ customers can be present, because after seating the pair there will be at most $16$.

Therefore

$$ n\le 14. $$

If every block contained at least one customer, then the total number of customers would be at least $8$. More importantly, if every block contained at least two customers, the total would be $16$, contradicting $n\le14$.

Hence some block contains at most one customer.

A pair requires an empty block. We must show that one exists.

Suppose, to the contrary, that every block were nonempty. Since each block then contains either one or two customers,

$$ n\ge 8. $$

For there to be no empty block, the minimum possible occupancy occurs when every block contains exactly one customer, giving $n=8$. But under our strategy a block containing exactly one customer contains a single customer seated at an end seat. Such a block still has two adjacent vacant seats available for a pair: in a 3-seat block, if the left end is occupied, seats $2$ and $3$ are free; if the right end is occupied, seats $1$ and $2$ are free. Thus any block with exactly one customer can receive a pair immediately.

Therefore a pair can be seated whenever some block has occupancy $0$ or $1$. Since $n\le14$, not all blocks can have occupancy $2$, so such a block always exists.

Hence a pair can always be seated.

Departures

Singles leave individually, and pairs leave together. When customers leave, the occupancy of a block decreases but the block remains in one of the allowed states listed above. Therefore the block structure and the seating rule are preserved after every departure.

Thus the invariant is maintained by both arrivals and departures.

We have shown that:

  1. every block always remains in one of the permitted states;
  2. a single arrival can always be placed in a block with occupancy at most $1$;
  3. a pair arrival can always be placed in a block with occupancy at most $1$;
  4. departures preserve the invariant.

Therefore the hostess can always seat every arriving group immediately, without splitting any pair and without ever assigning a single customer to seats

$$ 2,5,8,11,14,17,20, $$

provided that at no time are there more than $16$ customers present.

$\square$