All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Waiting, waiting... (Posted on 2004-08-07)
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!

 See The Solution Submitted by Federico Kereki Rating: 3.2857 (7 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 simulation | Comment 9 of 19 |

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

 Search: Search body:
Forums (0)