You are outside a well known restaurant, waiting in queue, with 18 couples in front of you. You know there are forty tables inside, and you think an average meal will take one hour.

How long will you have to wait, on average?

PS. This problem comes from queueing theory, but you don't have to know anything about it to find the answer!

The situation was simulated for 50,000 trials by

DEFDBL A-Z
DECLARE SUB sort (n1, n2)
CLEAR , , 4000
RANDOMIZE TIMER
DIM SHARED diner(40)
FOR tr = 1 TO 50000
   FOR i = 1 TO 40
     diner(i) = RND(1)
   NEXT
   sort 1, 40
   tot = tot + diner(19)
   trials = tr
   PRINT tot, trials, 60 * tot / trials
NEXT tr

SUB sort (n1, n2)

  IF n1 = n2 THEN EXIT SUB
  pvt = diner(n1)
  IF diner(n2) < pvt THEN pvt = diner(n2)
  DO
    i = n1 - 1: lower = 0
    DO
      i = i + 1
      IF i <= n2 THEN IF diner(i) < pvt THEN lower = i
    LOOP WHILE diner(i) <= pvt AND i <= n2
    IF i > n2 AND lower = 0 THEN EXIT SUB
    IF i > n2 THEN pvt = diner(lower)
  LOOP WHILE i > n2
  sw1 = i
  i = n2 + 1
  DO
    i = i - 1
  LOOP WHILE diner(i) > pvt AND i >= n1
  sw2 = i
  DO
    IF sw2 < sw1 THEN
      sort n1, sw1 - 1
      sort sw2 + 1, n2
      EXIT SUB
    END IF
    IF diner(sw1) > diner(sw2) THEN
        SWAP diner(sw1), diner(sw2)
    END IF
    DO
      sw1 = sw1 + 1
    LOOP UNTIL diner(sw1) > pvt OR sw1 > sw2
    DO WHILE sw2 >= sw1 AND diner(sw2) > pvt
      sw2 = sw2 - 1
    LOOP
  LOOP
END SUB

and the final tabulation verifies Nosher's solution:

23155.27175307274           50000         27.78632610368729

where the 23155.27175 is the total time spent waiting on 50,000 such queues, for an average time of 27.786 minutes, showing 27.75 minutes is probably the correct answer as opposed to 18.5 minutes.

Posted by Charlie on 2004-08-09 14:15:16