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, ...
******