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 AZ
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 20040809 14:15:16 