Fog Creek Software
Discussion Board


The solution given to the salary problem can be improved.

Let A add a random amount AR to its own salaray AS and hand it over to B. Now B can just add its salary to the amount given by A. C add its own salary to the amount received from C. Now A subtracts AR and gives the value of (AS+BS+CS) to the rest.

A only sees one value, which is from C and is equal to AS+AR+BS+CS. There is no way for it know B and C from this. Yes, it can compute BS+CS, which it can do anyways.

B only sees AS+AR and AS+BS+CS, there is no way it can calculate, CS or AS from these.

C only sees AS+BS+AR and AS+BS+CS, it can compute AR from this but it still cannot compute AS or BS.

If C informs B, what the AR is, B can compute AS but then it can also compute CS, which will be a detriment for C to do so.

The advantage here is that, the solution is faster. Needs only 2 rounds.

Alex Czar
Monday, June 30, 2003

It seems to me that there is a simpler way to do it:

1) Alice chooses a random number and keeps it to herself
2) Alice takes her salary and adds it to the random number, writing the result on a piece of paper
3) Alice passes the paper to Bob, who adds his salary to the old number, and writes the result on a new piece of paper
4) Bob passes the paper to Carol, who add her salary to the old number, and writes the result on a new piece of paper.
5) Bob passes the paper to Alice, who subtracts the secret random number and divides by three. 

Now the average salary is known, but only one random number is chosen and the "paper" is passed around only n times instead of 2n times (of course, it requires twice as much paper!).

Breckin Loggins - Loggins & Smith Software
Wednesday, July 16, 2003

Guess there is even simpler solution. The first person writes down any number (more or less her actual salary), then the second and the third persons add their real salary. Finally the person A completes the procedure, adding the rest (or removing the extra) and divides it by 3. Looks like it needs just 4/3 rounds.

Mike Faynberg
Tuesday, August 26, 2003

Instead of paper they can use computer program to input and calculate.
And the simplest way: coworkers take a closed box and everybody puts 1% of his/her salary there. Afterwards they spend money on drink :)

Vsevolod Chaikovsky
Thursday, July 01, 2004

*  Recent Topics

*  Fog Creek Home