Sunday Times Teaser 2823 – Queuing

by John Owen

Published: 30 October 2016 (link)

Tickets for the event went on sale at 0930. The queue started at 0900 when 2 people arrived, then 4 more at 0901, 6 more at 0902 and so on until 60 more arrived at 0929. Just 16 people arrived at 0930, 16 more at 0931, 16 more at 0932 and so on. Tickets were sold steadily at a rate of 25 per minute (one for each person in the queue).

Joe and I were the first to arrive at our respective minutes, but we had identical waiting times before being sold our tickets, and no-one waited for less time to get their ticket. Joe was lucky to get the last ticket to be sold.

At what time did Joe join the queue?

NOTE: This is a clarified version of the text published in the Sunday Times

One Comment Leave one →

Brian Gladman permalink


from itertools import count
from collections import defaultdict

# map the time a person waits in the queue to their one based
# ticket number and the time at which they joined
w2nm = defaultdict(list)

# the zero based ticket number for the next person in the queue 
ticket_nbr = 0

# the minutes past 09:00 (when the queue is extended)
for joined in count():
  
  # find the time (in 2.4 second units) when the
  # next person in the queue will be served 
  served = 750 + ticket_nbr
  
  # and the wait time in 2.4 second units
  wait = served - 25 * joined
  
  # exit when the queue is empty
  if wait <= 0:
    break

  # map the time waited to the one based ticket number
  # and the minute that the queue was joined
  w2nm[wait] += [(ticket_nbr + 1, joined)]

  # add the next group of people to the queue
  ticket_nbr += 2 * (joined + 1) if joined < 30 else 16
  
# find the minimum wait time shared by two or more people
w_min, min_list = [(w, w2nm[w]) for w in sorted(w2nm) if len(w2nm[w]) > 1][0]

# the ticket numbers and join times for the two people
(tn1, m1), (tn2, m2), *_ = min_list

# the queue joining times in hours and minutes
h1, m1 = divmod(540 + m1, 60)
h2, m2 = divmod(540 + m2, 60)

fs = 'I joined at {}:{:02}, Joe joined at {}:{:02} (we  got tickets {} and {}).'
print(fs.format(h1, m1, h2, m2, tn1, tn2))

from itertools import count

from collections import defaultdict

# map the time a person waits in the queue to their one based

# ticket number and the time at which they joined

w2nm = defaultdict(list)

# the zero based ticket number for the next person in the queue

ticket_nbr = 0

# the minutes past 09:00 (when the queue is extended)

for joined in count():

# find the time (in 2.4 second units) when the

# next person in the queue will be served

served = 750 + ticket_nbr

# and the wait time in 2.4 second units

wait = served - 25 * joined

# exit when the queue is empty

if wait <= 0:

break

# map the time waited to the one based ticket number

# and the minute that the queue was joined

w2nm[wait] += [(ticket_nbr + 1, joined)]

# add the next group of people to the queue

ticket_nbr += 2 * (joined + 1) if joined < 30 else 16

# find the minimum wait time shared by two or more people

w_min, min_list = [(w, w2nm[w]) for w in sorted(w2nm) if len(w2nm[w]) > 1][0]

# the ticket numbers and join times for the two people

(tn1, m1), (tn2, m2), *_ = min_list

# the queue joining times in hours and minutes

h1, m1 = divmod(540 + m1, 60)

h2, m2 = divmod(540 + m2, 60)

fs = 'I joined at {}:{:02}, Joe joined at {}:{:02} (we got tickets {} and {}).'

print(fs.format(h1, m1, h2, m2, tn1, tn2))

Here is a manual solution. Let \(t\) be the number of minutes after 09:00. Then, for people joining before 09:30, the number of people in the queue ahead of the first person to join at time \(t\) is \(t(t+1)\). And this person has a wait time of \[30-t+t(t+1)/25 = ((t-12)^2+606)/25\] Hence the minimum wait is 606/25 minutes. For those joining after 09:30, the wait time is \[(930-9(t-30))/25 = (1200-9t)/25\]Equating this with the earlier minimum wait gives his joining time as 66 minutes, which means that Joe joined the queue at 10:06.

Sunday Times Teaser 2823 – Queuing

by John Owen

Published: 30 October 2016 (link)

Leave a comment to Brian Gladman Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta