Quiet in the Depths

The need for near-silence in a submarine leads to strict procedures. As a submarine captain explained, “One of our drills, in case we are under conditions of extreme radio silence inside the submarine, is to exchange information among our five key departments. Naturally, we can’t tell you which those are.

“Each department consists of five sailors. Our basic protocol works as follows: As captain, I request certain information by broadcasting the request to all departments; each department responds with a number that is sent only to the captain (no broadcast); then the captain may broadcast a number; and so on. Remember, the captain broadcasts; the others don’t.

“To demonstrate, the departments will exchange very few messages with me - as few as possible - in order for me to determine some information. Naturally, we can’t reveal to you the nature of such information, but my first officer has come up with a sanitized version.”

Warm-Up

Suppose the captain broadcasts the request for the arithmetic mean of the blood pressures of all sailors in those departments. (“Blood pressure,” technically, systolic blood pressure, is the sanitization of a three digit quantity of interest.) Can the departments respond in such a way that the captain can then compute the mean?

Solution to Warm-Up

Each department calculates the mean of its sailors’ blood pressures and reports that number. The captain computes the sum of these means and divides by five. This works because each department has the same number of sailors (otherwise the captain would have had to weight each reported mean by the number of sailors in that department).

Okay, that was pretty easy. It turns out they weren’t so interested in the mean as in the median. (The mean is too sensitive to outliers.) But the median itself wasn’t necessary, simply a “blood pressure” among the 10 middle values of the 25.

1. Assuming blood pressures are three digits long, can each department report one three digit number so that the captain can infer a blood pressure among the 10 middle blood pressures of the 25 sailors?

2. The captain wants to find some blood pressure value that is sure to be less than or equal to the median and some blood pressure value that is sure to be greater than or equal to the median. Using the assumptions of the first question, can the captain infer such a value after one three-digit report from each department?