CentiMillionaire

Barrey gave us some background: "To enter this club, you must show a bank or stock account statement with $100 million dollars in it. Then you must be recommended by a committee of members. If you are worthy, you are chosen. Membership offers you visiting privileges to the most exclusive yacht, golf, and tennis clubs around the world, as well as priority for the penthouse suites of the world's greatest resort and metropolitan hotels from Zimbabwe to Zürich.

"Each year, there is an annual meeting on an island in the Caribbean owned by the club. There, the Centimillionaires meet and discuss new business ventures, many involving exclusive monopolies from mineral-rich nation states."

"The few get rich and the many walk barefoot in the mud," Ecco observed, his eyes narrowing.

"It's very complicated," Barrey replied quickly in his cheery voice, aiming for a lawyerly appeasement. "Some of these people are good and some are less good. What I'm asking you for today is help with a problem that has nothing to do with politics, merely with money."

Ecco scowled, but 11-year-old Liane was already sitting on the edge of her seat preparing for the puzzle.

Barrey continued, "We have 20 people around the world. They are all Centimillionaires, but none have more than $10 billion. They are rich enough, however, that they all round their wealth to the nearest $100 million. Several may have the same number of centimillions. They want to know how many centimillions the richest and poorest among the 20 have and how big those rich and poor subgroups are. Nobody should learn who else is in any subgroup (unless all or all but one are in some subgroup or there is large-scale collusion). You can assume that they will be honest in the information they give and in any calculations they are asked to do."

After a few seconds, Liane made her first observation, "Since they care about accuracy only to the nearest $100 million and since nobody is richer than $10 billion, there are only 100 possibilities. We can use the same logic here as we would with 20 people whose wealth fell between $1 and $100 where everyone estimated his or her wealth to the nearest dollar. Right?"

"True," said Barrey. "But then I wouldn't be their lawyer."

We all laughed. Even Ecco managed a smile.

"Let's see," said Liane. "If they all were in one room, then I could think of a fairly easy solution if you gave me 100 mailboxes."

Reader: Do you have any ideas?

"What would you do then, young lady?" Barrey asked.

"Well, I'd start by labeling each mailbox with a centimillion (1 centimillion, 2 centimillions,..., 100 centimillions) and I would lay them out in that order," Liane responded. "I'd give each centimillionaire 100 identical envelopes, 99 pieces of paper saying 'no,' and 1 piece saying 'yes.' Each centimillionaire would go to a private room where he or she would place the 'yes' in one of the envelopes and the 'no's in the other envelopes. Then the centimillionaire would place one envelope in each mailbox, putting the one with a 'yes' in the mailbox corresponding to his or her wealth."

"Nice work, Liane," I said.

"Thank you, Professor Scarlet," she replied, "but this does not help when they must communicate by phone."

"A promising young cryptographer named Camus Tiger once mentioned a trick," Ecco said. "It goes like this: If I am thinking of a number N that is known to be less than another number M, then I can give Alice, Bob, and Carol three numbers N1, N2, and N3, respectively (all smaller than M) such that (N1+N2+N3)mod M=N. Knowing even two of those numbers, nobody can infer my N. Maybe one could use that."

I looked at Ecco and knew that he had a solution in mind. But he said no more. He picked up a journal of genetics and started to read it. Barrey sat down with a sigh and stared up at the ceiling. Only Liane was active, scribbling on the paper, drawing tables of numbers.

Suddenly, she stopped, looked at Barrey and said, "I've got it. I can find the wealth of the poorest and the richest subgroups and how many are in each of those subgroups."

Liane explained her technique, taking full advantage of Camus Tiger's trick. Her method not only revealed the wealth of the poorest and richest centimillionairs, but also the sizes of the poorest and richest subgroups. That was what Barrey wanted. Her method leaked a bit more information as well: The number and wealth of all intermediate subgroups. Still, the method divulged no information identifying any individual.

Barrey listened to her explanation twice. He took notes, and showed them to Liane who corrected them. He reread them and then claimed that he understood. He reached into his pocket and pulled out a certified check and handed it to Ecco. Ecco put it on the table and led the visitor to the door.

After Barrey left, Ecco showed the check to Liane. It was for $300,000. "We'll put it in your college fund," he said. "At least some good will come out of these financial raptors."

Reader: Liane's solution requires that all 20 people communicate with each other at least once, nearly 200 phone calls. With her method, 19 people must collude to infer the 20th person's wealth. Try to find a method that finds the wealth of the richest and poorest subgroups, offers the same collusion protection as Liane's method (that is, at least 19 people must collude to infer the 20th's wealth), and can be done with as few phone calls as possible. First, try this by using the 20 centimillionaires only. Second, though Liane didn't try this, consider allowing outsiders to help but make sure that 19 people must collude to infer the wealth of any centimillionaire. Third, is there any way to do either the original problem or the second one with fewer phone calls?

Last Month's Solution

1. We are told that 2000 good pints of blood may be thrown away, given that there are 1000 bad pints. Suppose we divide the pints into 5770 groups of size 17 and 18. About 1/3 are of size 17 and the rest are of size 18. We test all the pints in each group for goodness. Approximately 1000 will be bad. Suppose they are all of size 18. We then divide each group of 18 into 6 subgroups of three. Any subgroup that is bad is thrown away. There cannot be more than 1000 of these. So, the total number of tests is 5770+6000=11,770.

2. If no good pints may be thrown away with the bad ones, then we can be sure of finding an answer with 20,000 tests, as follows: We divide up the 100,000 pints into groups of 10. In the worst case, 1000 groups will have bad pints and we then test all the pints among those 10,000. If fewer groups are bad, then we will have fewer than 10,000 individual pints to test.

3. Consider numbering the pints in binary. We need 17 bits:

0 0000 0000 0000 0000

0 0000 0000 0000 0001

0 0000 0000 0000 0010

and so on. Now test all pints with a 1 in the high-order position, then all pints with a 1 in the second most high-order position,..., and finally all pints with a 1 in the low-order position. The bad pint is the one whose ith bit (starting from the high-order position) is 1 if the ith test found a bad pint and is 0 otherwise.

4. Here is a method that finds all the bad ones in under 2000 tests: Test 1000 groups of 100 each. If 10 such groups are bad, then we know there is one pint in each group and we use binary search as above. Otherwise, we test the nine or fewer groups pint by pint. That is something less than 900 more tests.

5. Let's say there are two that are bad. Again, number the pints in binary. Test one bit. If both sides are 1, then do binary search on each half. If one side is 1, then discard the other half. So, at each bit, we reduce the problem size by a factor of 2. The total number of tests is something like 34. Unfortunately, this technique does not parallelize easily.

Reader Notes

In the "Sticks" problem (DDJ, February 2000), General Collins in fact presented a slight inconsistency regarding the stick mines, which Ecco ignored in his solution. The dimensions given by the general work for a park that is 7/8 kilometer tall rather than 1 kilometer tall. With the dimensions given, either K, J, I, V, and G would not be on the edge of the park or C, X, F, E, and D would not be. If the park is indeed 7/8 kilometer tall, then there are also some redundant hints, mostly vertical:

Q is 2 above P,

O is 2 above B,

M is 3 above X,

I is 1 above W,

W is 3 above L,

A is to the left and downward of P, and

C is to the right and downward of A.

With the correction to 7/8 of a kilometer, there is only one solution. Otherwise, there are an infinite number involving vertical translation. Some readers found other inconsistent constraints to drop, resulting in moving some points. A salute to all these clever readers: John A. Trono, Pike Enz, Tom Carmichael, Russ Williams, Pearl Pauling, Eden Mei, Andrew Palfreyman, Steven Bryant, Tomas G. Rokicki, Alan E. Dragoo, Dennis Yelle, Greg Smith, Jonathan Chen, Burghart Hoffrichter, Jimmy Hu, Christopher Creutzig, Paolo Friedli, David Berson and Prof. Dr. Michael Vielhaber.

DDJ