Now, suppose there are n job applicants J_1, \dots, J_n waiting on a line, in any order. We call them in for interviews using a_i as our "call list." More formally, for i = 1, \dots, 2n, we call J_{a_i} one by one.
If a particular job applicant J_x is called for an interview, he has to pay a fee of y-1 where y is his position in the line. For example, if he was the second person when called, he pays a fee of 1. If he was the front person, he doesn't pay. After the interview, he returns to the front of the line, and the interviewer proceeds with the next one on the call list.
For a given call list and initial ordering of applicants, we define income as the total fees paid by the applicants. For a given call list, its potential income is the sum of all income over all possible initial ordering of applicants. Now, to make things more interesting, before the interview day, the call list itself was shuffled, such that any (2n)! permutation is equally likely to appear.
If you are tasked with putting together a call list, knowing that it will eventually be shuffled, how should you structure it so that the expected potential income is maximized?
No comments:
Post a Comment