Puzzles for Programmers and Pros

4.3. Refuse and Reveal

One of the approaches to understanding a large amount of data is to characterize it using a few numbers. Statistics such as minimum, maximum, and the various kinds of averages tell you global properties. Sometimes they are enough to reveal information about individuals. This is why databases that give only statistical information are an issue for privacy advocates: Enough statistical questions can reveal personal data.

Consider a simple game between a questioner Quentin and a responder Rosalba. Quentin can ask only about global properties of a group of numbers, e.g., are they all whole numbers, are they distinct, and the statistics—mean, median, minimum, and maximum.

Rosalba always tells the truth. She may refuse to answer, however, if she knows the answer may divulge all the numbers. As we'll see, the refusal to answer may itself divulge all the numbers. Sometimes, she will volunteer information just for the fun of it.

4.3.1. Warm Up

Rosalba: "I have five integers, all distinct."

Quentin: "What is the minimum?"

Rosalba: "15."

Quentin: "What is the maximum?"

Rosalba: "I won't tell, because you would know everything."

What are the numbers?

4.3.2. Solution to Warm-Up

Because the numbers are all distinct, the maximum would tell everything only if it were 19. Then the collection consists of 15, 16, 17, 18, and 19. Okay, this was easy, but the deductions will get ...