On Firing Professors A Dean of Arts and Science, needing to find budget cuts, has decided to reduce the number of professors in the area of probability theory. There are currently five, and the Dean, whose reputation as a bean-counter is notorious, proposes a contest. A bag is produced containing 100 beans. Each professor in turn must take some beans from the bag. The ones who take the largest and the smallest numbers will be fired. (If two take the same number both will be fired.) The professors may not discuss their choices nor disclose how many beans they have taken. At his/her turn, however, a contestant may count how many beans remain in the bag. Each professor must take at least one bean. The beans need not be used up. The intent of each individual is to retain his/her post. Who has the greatest chance of doing so? ****** The original version of the problem involved the execution of prisoners. The setting has been changed to a more cut-throat environment, but the formulation of the problem itself is unaltered. Two of the rules are not adequately specified. Is it ties for the largest and smallest numbers, which seems obvious at first sight, or is it all ties, who will be fired? And does taking "at least one bean" imply "if any remain", or does the rule constrain each professor to leave enough beans for the successors? I believe that the second changes only minor details, and will assume that a professor is permitted to leave no beans for the successors. As to the first, I will consider both alternatives. The question itself is somewhat reminiscent of the problem of Josephus. Perhaps the Head of Mathematics wishes to protect one of the colleagues by arranging the order of choosing. Actually, the wording of the question itself is problematic. In some situations, professors have choices which control the fate of later colleagues while not altering their own. Thus, malice or "benefice", rather than chance, become major factors. All we can discuss, then, is the optimum strategy for each contestant. ****** The First Tie Variant Assume that it is only ties for top and bottom, NOT intermediate ties, that are to be fired. Let us call the professors (and their choices) P1, ..., P5 and, for the sake of gender neutrality assume that they are alternately female and male. Only P2 knows how many beans each predecessor has taken. The others, however, know the total, and therefore the average to date. Note that, unless all predecessors are tied, the average MUST be smaller than the current largest and larger than the current smallest. It is, of course, often fractional. In some circumstances, P3, P4 and P5 may be able to use this to find a safe position. We will return to this later. First, however, consider Strategy A, which can be used by P2, P3 and P4 if their predecessors have taken a lot of beans. Choose a number less than the average to date, and more than a quarter (for P2), a third (for P3), a half (for P4) of the remainder. If such a number exists, the first ensures that you are less than the highest. The second ensures that someone after you must take less than you. This works for P2 whenever P1 takes 21 beans or more. For example, if P1 takes 40, P2 can take anywhere from 16 (more than a quarter of 60) to 39. Suppose he takes 16; there are only 44 beans left, and one of the last three must take 15 or less. The corresponding limits: for P3, P1 + P2 > 40, for P4, P1 + P2 + P3 > 60. In the limiting case, common to all three, if P1 takes 21 beans, then P2 takes 20 (less than P1, more than a quarter of 79), leaving 59 between P3, P4 and P5, who cannot all match or exceed P2. P3 now takes 20 (less than the 20.5 average of P1 and P2, and more than a third of 59), leaving 39 between P4 and P5. P4 also takes 20 (less than the current 20.33 average and more than half of 39). Finally, P5 is stuck with a maximum of 19. Actually, in some circumstances, P2 can be nastier. For example, if P1 takes more than 50, P2 can take all the rest, condemning all of P3, P4 and P5. And P3 may have similar opportunities. Strategy B (The Averaging Strategy) A second possible strategy, available to P3, P4 and P5, is: Take the average of the choices of the predecessors, rounded to the nearest integer. If the average is an integer, this guarantees safety unless everyone is tied, provided that enough beans remain to allow it. If not enough beans remain, P3 and P4 can just take them all, ensuring that their successors have 0 (i.e. less than them). This second part, of course, does not help P5, but even P5 should do this in the hope that it places her above P1 or P2. If P1 > 50, "take them all" even serves P2. The Averaging strategy is used below in the situation where P1 < 21. The "not enough beans" situation no longer occurs there, since even P5 will find enough left for her purposes. ****** In Strategy A and Strategy B, P1 is one of the losers. She must therefore choose 1 <= P1 <= 20. In fact, P1 also does not want to be near either end of the range. P1 cannot choose 1, since this ensures that she is at best tied for low number. She cannot choose 2, because no subsequent professor will choose 1; nor 3, because P2 will not choose 2 because P3, P4 and P5 will not choose 1; and so on. Similarly P1 cannot choose 20 because P2 will not choose 21. (This would simply set up the 21, 20 situation with roles reversed and P2 as loser.) Nor 19, because P2 will not choose 20 because P3 will not choose 21; etc. P1 must therefore take a number r somewhere in the middle of the range, say, 10 or 12. The exact number doesn't matter. ****** It may clarify the direction of the discussion which follows if I reveal my claim: In the tie-variation under discussion, the puzzle is diabolical. (Did I mention that the Dean was a former professor of mathematics?) It has no solution in the sense that the reader is led to expect. If all the professors follow their "best" interests, ALL of them will be fired. They can diverge from their "best" interests and open up a safe position for later contestants; they may even save earlier colleagues; but they are sacrificing themselves. Furthermore, later contestants cannot tell with certainty whether such generosity has occurred, and can take advantage of it only by following the best- interest strategy, thus perpetuating the fatal path. To understand this, notice that if the highest and lowest numbers to date differ by more than 1, there is at least one safe number between them which all subsequent contestants can choose, PROVIDED that they can find it. Furthermore, the contestant who created this gap will be one of the losers. For example, (7, 8, 9) and (7, 7, 9) offer a safe haven at 8; (7, 8, 10) offers both 8 or 9. Can P3, P4 and P5 find out FOR CERTAIN whether such a situation exists? No, they cannot. But, except for one case, they CAN make a choice which finds a safe number if one exists, and does not create one which didn't exist. The choice is: THE CURRENT AVERAGE IF IT IS AN INTEGER; THE INTEGER NEAREST THE CURRENT AVERAGE, IF IT IS NOT. The exception, which applies to P5 only, arises if the previous choices were (r, r, r, r + 2) or (r - 1, r + 1, r + 1, r + 1). (8, 8, 8, 10) and (7, 9, 9, 9), for example, each have average 8.5. This needs to be rounded up in the first case, down in the second, but P5 has no way to know which to do. No such problem arises for P3. If, for example, P1 and P2 choose (7, 10), with average 8.5, either rounding is safe. P4 never sees an average with 0.5. As for P2, he must not create a safe number, and so must choose P1 or a number consecutive with P1. If he chooses P1, then the averaging strategy propounded above causes every contestant to choose P1. If he chooses P1 - 1, all subsequent contestants will choose one of P1 and P1 - 1. In both cases, all professors will be fired, as stated earlier. Any of the competitors can depart from their "best" choice, but this will generally cause them to miss any earlier sacrifice, unless the "gap" was more than minimal. In effect, the clever Dean has gained five positions for the budget, rather than two. ****** The Second Tie Variant Let us turn to the situation if ALL ties, even intermediate ones, are fired. In this situation, the Averaging Strategy, used above, can be applied only in the rare cases where it is unlikely to produce a tie. It is also necessary to change Strategy A to prevent ties. For example, if P1 takes 40 beans, leaving 60, it is not good enough for P2 to take 16 (just over a quarter of the remainder), leaving 44. Although this ensures that at least one later colleague takes less than 16, it does not prevent a tie. For this, P2 (and P3 and P4) must take more than half of the remainder. In the limiting case, if P1 takes 35, leaving 65, and P2 must take 33 (or 34) leaving 32. Now P3 cannot reach or exceed P2, and must take at least 17, to prevent P4 reaching or exceeding her, and so on. Again, P1 must take a smallish number. In fact, it should be small enough to allow all colleagues to exceed her if they choose. About 10 or 12 looks fine. The obvious strategy in this situation is for each professor to choose a number adjacent to the (block of) numbers chosen previously. (We will look briefly at alternatives later.) This prevents ties, while allowing the maximum chance that later choices will surround you. For the rest of this discussion, I will use numerical examples, and have P1 choose 7. (This number may be too small, but this doesn't affect the argument.) It makes no difference to the outcome whether P2 chooses 8 (up) or 6 (down). Assume he chooses 6. P3, seeing that 13 beans have been taken, will assume that this is 6 and 7, and therefore chooses 5 or 8. Call these values D and U (for down and up) respectively. P4 and P5 then have analogous options. P1 will lose only if the last three choices are DDD, apparently a 1/8 chance. P2 will lose only if they are UUU, also a 1/8 chance. P3 loses only if the last three, including her own, are DUU or UDD (i.e. she goes above the block and the next two go below, or vice versa), a 1/4 chance. P4's chances are 1/2. And P5? She has no chance at all. So the chances of surviving the purge seem to be: P1 7/8 P2 7/8 P3 3/4 P4 1/2 P5 0 Is that a probabilistic end of the story? A resounding NO. The problem is with the unfairly treated P5. At the outset, she has no chance of surviving the cut, and no reason to go along with the plan. Nonetheless, she controls the whole outcome. Faced with four successive numbers, say, 6, 7, 8, 9, she may quietly choose 5 or 10, as the above plan assumes, or with nothing to lose, may choose to tie one of the others. If she chooses 6 or 9, she and the two extremes are fired; if she chooses 7 or 8, four of the colleagues are fired. (Can she determine what the numbers are? Yes. Four successive numbers must total 4u + 2 for some u. The numbers start with u - 1.) Once again, malice, benefice or revenge on her colleagues for her treatment, rather than chance, decide the outcome. The Dean strikes again, saving two to four positions. ****** Consider other possibilities for P2. If P1 chooses 7, can P2 do better than 6 or 8? Suppose he chooses 5; then P3 sees 12 (even) rather than 13 or 15, and can safely choose 6. (Surely P2 didn't deliberately tie P1.) P4 is presented with the same situation as before. Seeing 18, he assumes that this to be 5, 6 and 7, which it is. In effect, P2 has increased P3's chances to 1, reducing his and P1's to 3/4, all subject to P5's later behaviour. Suppose P2 chooses 4; then P3 sees 11, assumes 5 and 6, chooses 4 or 7 If he chooses 4, P4 sees 15, assumes 4, 5, 6, chooses 3 or 7; if he chooses 7, P4 sees 18, assumes 5, 6, 7, chooses 4 or 8. None of these improve P2's or P1's chances. (By the way, in all these cases, P5 still sees 4u + 2, and doesn't know that anything unusual has occurred.) There are many other cases, which the reader is free to examine, but the further P2 gets from 6 or 8, the worse things are for him. ****** Epilogue The professors naturally asked for time to research the topic and write a paper. In the two years it took for this to be written, refereed and published in an obscure journal, the situation resolved itself. The Evil Dean was removed from office (he was actually promoted to University President), and as his salary was twice that of any of the professors, the Faculty budget became balanced, and the professors, now tenured, slept happily ever after. Eventually, however, the President felt that he had to appoint a new Dean. To find the salary, he decided that the five Associate Deans should be reduced by two. Reaching for his beanbag, ... ******