Teaser 2823: Queuing
From The Sunday Times, 30th October 2016 [link] [link]
Tickets for the event went on sale at 09:30. The queue started at 09:00 when 2 people arrived, then 4 more at 09:01, 6 more at 09:02 and so on until 60 more arrived at 09:29. Just 16 people arrived at 09:30, 16 more at 09:31, 16 more at 09:32 and so on. Tickets were sold steadily at a rate of 25 per minute (one per person).
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 a ticket. Joe was lucky to get the last ticket to be sold.
At what time did Joe join the queue?
This version of the text is provided by the setter, and differs from the version published in The Sunday Times.
[teaser2823]
S2T2 
Jim Randell 8:58 am on 21 September 2021 Permalink |
The problem with this puzzle (particularly in the form it was published in the newspaper) was working out the intended mechanics of the situation.
We suppose that all people joining the queue, do so simultaneously at the start of each specified minute. And that when the tickets are sold, they sold sequentially (a single ticket booth), with each sale taking exactly 1/25 minute (= 0.04m = 2.4s). This is apparently what the setter intended.
The following Python program simulates the sale of tickets as described, and looks for minimal wait times that occur for the first member of a joining clump, until the value is repeated (then the earlier one is the setter, and the later one Joe, and Joe gets the last ticket, so sales end).
It produces a log of events as it goes, and runs in 72ms.
Run: [ @replit ]
from enigma import irange, inf, sprintf, printf # format a time, (m=0, f=0) = 09:00.00 def fmt(m, f=0): (h, m) = divmod(m, 60) return sprintf("{h:02d}:{m:02d}.{f:02d}", h=h + 9, f=4 * f) # the queue, record groups as (number of people, start minute) q = [(0, -1)] # extend the queue, add n people with value m def extend(q, n, m): if n > 0: q.append((n, m)) # pop the queue, identifying the first in a group, return (x, flag) def pop(q): ((n, m), flag) = (q[0], 0) if n == 0: # move on to the next group q.pop(0) ((n, m), flag) = (q[0], 1) q[0] = (n - 1, m) return (m, flag) # size of the queue def size(q): return sum(n for (n, m) in q) # t = tickets sold # W = shortest waiting time # data = information for minimal wait times (t, W, data) = (0, inf, None) # run a timer for i in irange(0, inf): # m = minutes, f = fractions (1/25) of a minute (m, f) = divmod(i, 25) # on the minute if f == 0: # up to 09:29, 2m + 2 people join the queue # afterwards, 16 people join the queue n = (2 * m + 2 if m < 30 else 16) extend(q, n, m) printf("time {i}: added {n} people to queue, queue length = {q}", i=fmt(m, f), q=size(q)) # from 9:30, one ticket is sold per frame if m > 29: t += 1 # calculate waiting time (in frames) (x, flag) = pop(q) w = 25 * (m - x) + f printf("time {i}: joined at {x}, waited {w} frames, ticket {t}", i=fmt(m, f), x=fmt(x)) # is this a new minimum? if not(w > W): printf("-> min wait = {w} frames for ticket {t}") if w < W: W = w data = list() # is this the first in their group? if flag: # record data data.append((x, m, f, t)) # are we done? if len(data) == 2: printf("-> sold out after ticket {t}, queue length = {q}\n", q=size(q)) # output solution for (n, (x, m, f, t)) in enumerate(data, start=1): printf("{n} joined at {x}, served at {m}, ticket {t}", x=fmt(x), m=fmt(m, f)) breakSolution: Joe joined the queue at 10:06.
The minimal wait time is 24.24 minutes (= 606/25 minutes).
When the 1507 tickets sell out there are 399 people remaining in the queue.
The setter joined the queue at 09:12, and got the 157th ticket at 09:36.24.
Joe joined the queue at 10:06, and got the 1507th (and final) ticket at 10:30.24.
So, if the tickets are numbered consecutively from 1, the digit sum of the two tickets is the same (and if they are numbered with leading zeros where necessary, the ticket numbers are anagrams of each other).
LikeLike
Jim Randell 9:03 am on 21 September 2021 Permalink |
The puzzle text as originally published in the newspaper read as follows:
My interpretation of this was that people joined the queue simultaneously at the start of a minute. And when the tickets were sold, the 25 people at the head of the queue were processed simultaneously, at the start of each minute. (You can suppose there are 25 ticket booths, and each transaction takes exactly one minute). The wait times will always be whole numbers of minutes.
The main problem I came across with this method was that we don’t know how many tickets there are (it is implied that they sell out at some point), but if we suppose Joe is in the last batch of 25 tickets sold we can solve the problem.
Here is my code adapted to process the tickets 25 at a time.
from enigma import irange, inf, sprintf, printf # format a time, m=0 = 09:00 def fmt(m): (h, m) = divmod(m, 60) return sprintf("{h:02d}:{m:02d}", h=h + 9) # the queue, record groups as (number of people, start minute) q = [(0, -1)] # extend the queue, add n people with value m def extend(q, n, m): if n > 0: q.append((n, m)) # pop the queue, identifying the first in a group, return (x, flag) def pop(q): ((n, m), flag) = (q[0], 0) if n == 0: # move on to the next group q.pop(0) ((n, m), flag) = (q[0], 1) q[0] = (n - 1, m) return (m, flag) # size of the queue def size(q): return sum(n for (n, m) in q) # t = tickets sold # W = shortest waiting time # data = information for minimal wait times (t, W, data) = (0, inf, None) # run a timer (in minutes) for m in irange(0, inf): # up to 9:29, 2m + 2 people join the queue # afterwards, 16 people join the queue n = (2 * m + 2 if m < 30 else 16) extend(q, n, m) printf("time {m}: added {n} people to queue, queue length = {q}", m=fmt(m), q=size(q)) # from 9:30, 25 tickets are processed per minute if m > 29: for _ in irange(1, min(25, size(q))): t += 1 # calculate waiting time (in frames) (x, flag) = pop(q) w = m - x printf("time {m}: joined at {x}, waited {w} minutes, ticket {t}", m=fmt(m), x=fmt(x)) # is this a new minimum? if not(w > W): printf("-> min wait = {w} minutes for ticket {t}{s}", s=(' [first]' if flag else '')) if w < W: W = w data = list() # is this the first in their group? if flag: # record data data.append((x, m, t)) # are we done? if len(data) > 1: printf("\nsold out after {t} tickets, min wait = {w} minutes, queue length = {q}", q=size(q)) # output solution for (n, (x, m, t)) in enumerate(data, start=1): printf("{n} joined at {x}, served at {m}, ticket {t}", x=fmt(x), m=fmt(m)) printf() breakWe get the solution:
LikeLike