Calculation in the Narrows

Dennis, a professor of computer science at New York University, is the author of four puzzle books. He can be contacted at [email protected].

Last Month's Solution

Ecco was invited to a submarine base, where he heard about a new naval computational technique called "parallel local computation" (PALC). He was told it was very useful for high security applications, but they couldn't tell him which. Instead, they presented him with the following sanitized version of a problem commanders face:

A group of people have lined up in a long narrow corridor that allows only two people to be side-by-side. Each has been given a number between 1 and 10,000. After some number of rounds (described below), each person is to report a whole number that is no more than one above or one below the mean of the numbers. For example, if there are four people and they have been given the numbers 2, 2, 2, 3; then it is fine if some report 2 and some report 3 because the mean is 2.25.

During the course of this calculation, no person should have to remember more than five significant digits in total including those to the left and those to the right of the decimal point.

Because the corridor is so narrow, the people are going to move as shown in the example of Figure 1 for five people P0,...,P4. Only when two people are side-by-side can they exchange information. Note that in the first round, P0 encounters P1 and P3; P1 encounters P0, P2, and P4; and P2 encounters P1 and P3.

In each pairwise encounter, people can exchange numbers and do any calculation they like with those numbers. However, the number that each person retains after an encounter may contain no more than five digits.

Warm-Up: Suppose that two people A and B meet and that initially A's number x is greater than B's number y. Suppose the mean of the entire collection, while unknown to A or B, is denoted M_all. Consider the initial error of A and B to be the maximum of |x-M_all| and |y-M_all|. What can A and B do that will reduce their error without preventing them from calculating the mean correctly?

Solution to Warm-Up: They calculate the mean of x and y, denoted M_xy. A substitutes M_xy for x, and B substitutes M_xy for y. If M_all is greater than M_xy, then |M_all-y| was the error before, so the error is reduced.

Here is a proof: Suppose that x<M_all, then the order of elements is y<M_xy<x <M_all, so the conclusion follows. If M_all<x, then the order must be y<M_xy< M_all<x. Because M_xy is the mean of x and y, (M_xy-y)=(x-M_xy), which is greater than both x-M_all and M_all- M_xy.

So the error is reduced and the sum of all numbers stays the same.

We have ignored rounding so far. If rounding is required, then allow A, because it initially has a higher value, to take a value above the mean, and B to take a value below the mean in such a way that A loses as much as B gains. This guarantees that the mean of the results equals the mean of the inputs. End of warm-up.

The warm-up suggests the following possible solution. Each exchange rounds to the nearest whole number (always keeping the sum of all numbers constant). For example, in an exchange between 53 and 42, the resulting numbers would be 48 and 47. So the initially greater number would be given the higher integer.

1. Might there be some configuration of a dozen people and their initial values that requires more than 20 rounds in this case? What is the maximum necessary? The answer to this might suggest that using a number including one decimal digit would help.
2. If one does use a decimal digit for all numbers below 10,000 and there are at least 12 people in the hallway, then will any initial configuration require more than 20 rounds? What is the maximum necessary?
3. Suppose there could be only three people in the hallway. (I use three because two would have a solution in one exchange.) Then will any initial configuration require more than 20 rounds?
4. The protocol now requires that the person having the higher initial value gets the higher value after rounding. What if the assignment to higher or lower occurs randomly (with equal probability for the initially higher and initially lower)? Would this change the answer to question 1?

Here is an open problem. Consider a protocol in which after every exchange (rather than after every round), the list reverses itself. So the protocol looks like Figure 2 in a typical round.

Even though each round is more expensive, I cannot find a case involving 10 or more people in which the protocol takes more than six rounds provided one can use one digit to the right of the decimal point. Can you find a limit in terms of the number of rounds required?

DDJ