The summer holiday lies behind us and we have all gradually adjusted back to university life. Indeed, some of us might already be getting nervous for the exams. This edition’s puzzle considers exactly that, although from a slightly different perspective.
An econometrics student has an appointment with a professor for an oral exam in a university building with seven floors. However, just before his arrival, he loses confidence and decides to leave. Unfortunately for him, a thunderstorm appears outside the building, so leaving is not an option. The professor has noticed the student entering the building and starts looking for him.
Suppose the professor does not know at which floor the student is when he starts his search. The student can use the stairs to move up or down one floor. He makes such a move every minute. The professor takes the elevator and can move to any of the seven floors (including the one he is currently at) every minute. The professor is unaware of the whereabouts of the student, unless they find themselves to be at the same floor. The professor and the student perform their moves simultaneously.
Is there a sequence of floor visits which the professor can perform, to be certain that he finds the student in a finite amount of time? If so, on which floor should he start and what should his floor visit sequence be?
Please send your solution to nekst@Asset-Econometrics.nl before November 26. A crate of beer or a delicious pie, whichever the winner prefers, will be waiting for whoever has the best (partial) solution. Please note that, as before, every recipient of this magazine is eligible to send in their solution, so members of the department are invited to participate as well. Good luck!
Pascal Janssen is the winner of the previous puzzle. As a reward, he can come and pick up a crate of beer or a pie at room E1.10. The solution of the previous puzzle was 39.5.
Explanation Puzzle Nekst 4 2014-2015
The puzzle of Nekst 4 concerned a chef who sneezed over the soup he was preparing, thereby dropping exactly fifty droplets of nasal discharge in a bowl containing a hundred soup portions. The question that had to be answered was: what is the expected amount of bowls that will be infected, i.e. the number of bowls that contain at least one droplet of nasal discharge?
If I am completely honest, I will have to admit that there was no specific reason why the story had to be so distasteful. The question remained the same when the story told of a pot with melted gold containing fifty pieces of contamination, or in the most plain way: if you divide fifty balls at random over a hundred cups, how many cups are expected to remain empty? Now, let us solve that problem!
We first look at the more general problem, concerning m balls and n cups. Define X as the number of cups that remain empty. Define Yi as a row of ones and zeros depending on whether the ith cup remains full (implying 0) or empty (implying 1). Then X = Y1 + Y2 + … + Yn and E[X] = E[Y1 + Y2 + … + Yn] = E[Y1] + E[Y2] + … + E[Yn]. Note that even though the Yi’s are dependent on each other, the expected values can still be split.
E[Yi] = 0 * P[Yi = 0] + 1 * P[Yi = 1] = P[Yi = 1].
We now take a look at cup i. We know that the probability of a specific ball not being in cup i is 1-1/n, hence the probability that m balls are all not in cup I is (1 – 1/n)m. Therefore, E[Yi] = P[Yi = 1] = (1 – 1/n)m and so E[X] = n * (1 – 1/n)m. If we now plug in the values n = 100 and m = 50, we find that E[X] ≈ 60.5.
Therefore, if fifty droplets of nasal discharge are randomly dispersed over a hundred bowls of soup, the expected number of bowls that will not be infected is 60.5. This is bad news for company X, as probably 39.5% of its employees will not show up the day after the feast!