A puzzle beneath the waves.

October 01, 2005
URL:http://www.drdobbs.com/parallel/calculation-in-the-narrows/184406299

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

Start:
   P0 P1 P2 P3 P4
Next:
      P1 P2 P3 P4
      P0
Next (so, P1 and P2 can exchange information as can P0 and P3):
         P2 P3 P4
         P1 P0
Next:
            P3 P4
            P2 P1 P0
Next:
               P4
               P3 P2 P1 P0
End of round
Next:
   P4 P3 P2 P1 P0
Next (now P4 leads):
   P3 P2 P1 P0
   P4
Next:
   P2 P1 P0
   P3 P4
Next:
   P1 P0
   P2 P3 P4
Next:
      P0
      P1 P2 P3 P4
Next:
   P0 P1 P2 P3 P4
end of second round

Figure 1: People moving in a corridor.

Start:
   P0 P1 P2 P3 P4
Next:
      P1 P2 P3 P4
      P0
Next (reverse):
      P4 P3 P2 P1 P0
Next:
         P2 P1 P0
         P3 P4
Next:
     P0 P1 P2 P3 P4
Next:
            P3 P4
            P2 P1 P0
Next:
      P4 P3 P2 P1 P0
Next:
               P0
               P1 P2 P3 P4
End of round

Figure 2: List reversal.

Dr. Ecco Solution

Solution to "Maximum Lottery," DDJ, September 2005.

Following the idea of the sultan's daughters problem, we will express our protocols by three numbers in increasing order: x, y, and z. The idea is to reject the first x, then choose the next one better than those first x. Call the position of that one p1 (so p1>x).

If p1>y then choose the next one better than any seen before (at a position we'll call p2). Otherwise, reject until position y and then pick the next one better than any seen before (at a position we'll still call p2).

If p2>z, then choose the next one better than any seen before (at a position called p3). Otherwise, reject until position z and then pick the next one better than any seen before (at a position we'll call p3).

For 100 balls in total and three keeps, you win roughly 68 percent of the time if you set x, y, and z to be 14, 32, and 64, respectively. Here is one example win for the following sequence:

3 78 80 90 25 95 51 27 57 40 65 48 55 72 26 73 54 31 15 2 89 61 97 98 8 50 38 18
88 52 4 42 68 16 62 9 94 99 20 28 56 58 76 93 10 96 63 35 81 91 66 11 30 5 0 24
82 29 41 12 47 71 44 92 43 32 85 84 7 59 60 86 69 21 83 79 64 67 74 37 1 46 22
19 33 39 87 45 36 13 23 75 34 70 53 49 77 17 6 14

The p1 position value in this case would be 23 where the value 97 is found, because 97 is the first value larger than 90, which is the largest of the first 14 numbers. The p2 value would be 38 where 99 is found and the third keep then is irrelevant.

Reader Improvements Concerning "Treasure Arrow"

Alan Dragoo pointed out that the delta is 15 centimeters so the arrow and plank each weigh 75 kilograms. Carl Smotricz noted that because the arrow is not quite horizontal, the horizontal distance between the two ends of the arrow is less than 10 meters. In fact, it is (10²-(0.6)²)= 9.98. So, the arrowhead has dipped 0.6 meters for each 9.98 meters of horizontal distance. Continuing this line (Carl used trigonometry, but let's do this in a more elementary way), there would be a further dip of some amount x for the next 10 meters of horizontal distance. So, x=0.6×(10/9.98). This gives an extra 0.601 meters. So the arrow, in fact, points to 2.201 meters below the ceiling.

DDJ

Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.