Riddler Classic, February 28 2020

When I first saw this one, I thought it might be a chance to use some of the Erlang queueing equations, which I’ve known about for ages but never used seriously. Instead, I think it’s a bit easier than that. I missed the cutoff for having my name picked though!
 


 
At your local barbershop, there are always four barbers working simultaneously. Each haircut takes exactly 15 minutes, and there’s almost always one or more customers waiting their turn on a first-come, first-served basis.
 
Being a regular, you prefer to get your hair cut by the owner, Tiffany. If one of the other three chairs opens up, and it’s your turn, you’ll say, “No thanks, I’m waiting for Tiffany.” The person behind you in line will then be offered the open chair, and you’ll remain at the front of the line until Tiffany is available. Unfortunately, you’re not alone in requesting Tiffany — a quarter of the other customers will hold out for Tiffany, while no one will hold out for any of the other barbers.
 
One Friday morning, you arrive at the barber shop to see that all four barbers are cutting hair, and there is one customer waiting. You have no idea how far along any of the barbers is in their haircuts, and you don’t know whether or not the customer in line will hold out for Tiffany.
 
What is the expected wait time for getting a haircut from Tiffany?
 

 
I got to the answer in two different ways, and I think I understand it, so now I’m around 70% confident. That’s on the high side for a Riddler Classic, for me. (Side note, I think the new setter is easier than the previous one was!)
 
The first way I handled this was to simulate it in Excel. The model is in the first tab of this spread sheet, but the short version of what it does is simulate ten thousand trips to the hairdresser, with the same unknowns, and see how long it takes to get served.
 
Each of the trips is represented by a row in the first tab of spread sheet. The first four values in each row (columns A to D)  are four randomly generated times between zero and fifteen minutes, one for Tiffany and one for each of the other three barbers. These represent the time until each individual barber finishes with their current customer and becomes available for another customer. With those numbers set, in column K we calculate when the first queueing customer will be served if they wait for Tiffany (which is the same as, “when is Tiffany free?”), and in column N we calculate when that customer is served when they do not wait for Tiffany (which is just, “when will the next barber be available?”).
 
If the first queueing customer waits for Tiffany, I will be served 15 minutes later (column L), and even if they don’t deliberately wait for Tiffany, they might still be served by her. If that happens, there’s a TRUE in column M, and I am served 15 minutes later (column O). If the queueing customer does not wait for Tiffany, and is not served by Tiffany, then I only need to wait for her to become available (column O again).
 
Since we know from the problem that there’s a 25% chance that the queueing customer will wait for Tiffany, we can then weight the two possible results, three-to-one, and this is in column P. It’s the time we would expect to wait if we knew how much longer the four barbers needed until they were free, but we didn’t know whether the queueing customer needed would wait for Tiffany. The column P time is not a real waiting time, because the customer will either wait for Tiffany or not, in which case our waiting time will be respectively longer or shorter than this expected time.
 
Lastly in cell W4 there’s an average of all ten thousand expected wait times. This will vary if the random numbers are reset, but typically it’s a little over 14 minutes. At this point I didn’t know why it was such an odd number. There are more average values in R4 to V4, and I can understand and explain them, but not this one.
 

 
The second way I handled this sprung from my problem with the first way: I wanted an exact solution, and to understand it. Since I already have a model that calculates times, I can build a decision tree instead. If we know the expected times at which staff become available, then there are really only two things that vary from case to case:
  1. Will the queueing customer wait for Tiffany, and
  2. If he won’t wait for her, will he be served by her anyway?
These two questions are easy to answer, so this turns out to be a quick way of calculating the expected wait time. One way of representing the decision tree is in the second tab of the spread sheet. This is what it looks like:
 
 
The “tree” is in the shaded area; read it from the top to the bottom.
 
There are three branches, each with different expected wait times. The weights for each branch (the percentages) come straight from the question. The expected wait at the end of is how long we expect to wait if the decisions on that branch of the tree are true.
 
The expected waits are fairly straightforward. If the queueing customer doesn’t wait for Tiffany and isn’t served by her, then Tiffany will be the second, third, or fourth barber to finish. She can’t be the first to finish in this case, so she will take longer than 7.5 minutes on average. If the queuing customer doesn’t wait for her but is served by her, then she must have been the first barber to finish. If the first customer will wait for Tiffany, then we don’t know how soon she will finish, so we expect to wait an average length of time for her to finish (7.5 minutes) plus 15 minutes for the queueing customer.
 
My total expected wait time is the sum of the weighted times on each branch of the tree, 14 and one-sixteenth of a minute.
 

Leave a Reply

Your email address will not be published. Required fields are marked *

I accept that my given data and my IP address is sent to a server in the USA only for the purpose of spam prevention through the Akismet program.More information on Akismet and GDPR.

This site uses Akismet to reduce spam. Learn how your comment data is processed.