Riddler Express – 12/21/2018

This week’s Riddler Express is about Santa hitching up the reindeer. He does not remember the order of the reindeer, with the exception of that showoff Rudolph. The reindeer can tell Santa if they are in the correct position, but cannot tell any more information.

Santa’s solution is to try the reindeer one at a time at the front of the sleigh until he gets the correct one. Then, he moves on to the next position. It takes Santa one minute to hitch up one reindeer. The question is to find out how long to expect this process to take. The answer is below.

The expected time to get all reindeer in the correct position is 22 minutes.

To do this calculation, we need to total a few finite sums. The formulas we will use are from Calculus.

Suppose we start with $n$ reindeer and want to get the correct reindeer in the given position. There is a $\frac{1}{n}$ probability we will get it right the first time, taking one minute. There is also a $\frac{1}{n}$ probability we will get it right the second time, taking two minutes. We can continue this pattern for all $n$ reindeer. This means the expected time to get one reindeer out of $n$ in the correct position is $\displaystyle \sum_{i=1}^{n} \frac{1}{n} i = \frac{1}{n} \sum_{i=1}^{n} i = \frac{1}{n} \frac{n(n+1)}{2} = \frac{n+1}{2}$.

To find the expected completion time for all eight positions, we add up the expected times to place one reindeer out of eight, then one out of seven, and so on. This leads to the following sum. $\displaystyle \sum_{i=1}^{8} \frac{i+1}{2} = \frac{1}{2} \left( \sum_{i=1}^{8} i + \sum_{i=1}^{8} 1 \right) = \frac{1}{2} (36 + 8) = 22$

To double-check my calculations, I used the following R script.

first_sort <- function() {
minutes = order[j]) minutes <- minutes + 1
if (i == order[j]) break
}
}
return(minutes)
}

trials <- c()
for(i in 1:25000) trials[i] <- first_sort()
print(mean(trials))

(The code display seems broken for some reason.)

The extra credit question asks if there is a strategy that Santa can use to speed up the process. I feel that there is one, but I cannot think of it.

The algorithm Santa is using is very similar to a selection sort type of algorithm. The running time for this sort is $O(n^2)$. There are faster sorting algorithms, such as heap sort, that have a faster running time of $O(n \log{n})$. However, I am not able to think of a way to use these faster sorting algorithms on the reindeer.