What's our average salary?
There are 3 colleagues who want to know what their average salary is, but they do not want to disclose to each other their individual salary. How do they go about doing it? In the process of doing it what is the worst that each could learn about the salaries of the other two? Is this method fail-proof? Think about it! Would you be willing to adopt your methodology with your colleagues and find the average salary?Level: Medium
posted by Karthik Nagaraj at
5:40 PM
10 Comments:
Each person uses a simple cryptography algorithm to encrypt his salary.
Example, suppose Person A uses the algorithm called “Plus 2”. He adds 2 to each digit of his salary.
A salary of 9230 would become 1452.
Similarly B and C choose a encrypting number say 1 and 3.
Now, they put the encrypted salaries on a piece of paper and drop it into a box. One designated person amongst them picks up all the 3 slips.
All three reveal their secret codes. The sum of their codes in this example would be 6.
The designated person adds the 3 encrypted numbers from the 3 slips. He subtracts 6 from each digit. He has the total salary now. He divides it by three.
The designated person knows which piece of paper is his, but he cannot know with certainty whose the other two slips are. He can only guess, but can never be sure.
Is this the right solution, or did I think too laterally? : -)
Just realized that with such a simple encryption algo, the designated guy can easily figure out the salaries of the other two.
might as well scrap the above solution :)
Not a very intuitive answer.
Here it goes.
We can have a simple programme written which takes in 3 numbers as input one after another and clears the screen before taking in each input.It divides the sum of these by 3 in the end and flashes the input..We can have the 3 persons key in their salaries in turns without each one looking what the other is keying in (say like in a polling booth).
A small correction...
Not a very intuitive answer.
Here it goes.
We can have a simple programme written which takes in 3 numbers as input one after another and clears the screen before taking in each input.It divides the sum of these by 3 in the end and flashes the output..We can have the 3 persons key in their salaries in turns without each one looking what the other is keying in (say like in a polling booth).
Mohit and Mayura,
Welcome aboard! Mohit, as you rightly guessed your solution will reveal the salaries of the other 2. Thats not acceptable to these 3 guys. Now Mayura, there is no fun in having to write this program and then ask them to feed in the numbers, right? For all you know each of these guys could have a memory sniffer or a keystroke recording software that can very easily identify the salaries entered. So I'm sorry to say, the solution is not correct.
But, Mohit is thinking on the right lines, only thing make sure the solution does not reveal the individual salaries to each other.
Clue: Why do you want to add a number to each digit?
Hmm... how about this?
The three people reveal their encryption keys to a fourth person D.
D then reveals the sum of the three keys to the group and the designated person in the group picks up the three slips... adds the numbers and decrypts.
Mohit,
Again you are missing the point. Encryption keys are private and cannot be revealed to anyone but to yourself. So if you were to reveal it to the 4th guy, then he can find out the individual salaries of the 3 people right? Devise a mechanism in which only the 3 people are involved and they need to know the average of their salaries.
suppose the persons involved are A,B,C and their salaries are 3000,4000 and 5000 respectively.
We have
A=3000
B=4000
C=5000
A guesses some number say 2 and performs say addition to his salary.i.e. now 3002.This he reveals to the other ppl.
Similarly B guesses say 5 and performs some operation say multiply and reveals the output to the other people.i.e. 20000
Similarly C guesses some number say 6 and performs some operation say subtraction. i.e. 4994
Each one is not aware of the number guessed and the operation performed by the other.They are only aware of the result.
Now the average is computed.
(3002 + 20000 + 4994)/3 = 9332 (A1)
Now A undoes what ever he has done before
i.e. he subtracts 3002/3 from 9332 and adds his (actual salary /3) to the result.
9332-3002/3+3000/3=27994/3 (A2)
He reveals only A2 to the others.
Similarly B undoes what he has done before on A2 and recorrects the average.
So
27994/3-20000/3+4000/3=11994/3(A3)
He reveals only A3.
Similarly C undoes what he has done before on A3 and recorrects the average.
So
11994/3-4994/3+5000/3=12000/3=4000(A4)
A4 is the actual average and the individual salaries of each are also not revealed in the process as the number and operation performed by each person was kept a secret from others and only the result was revealed.
Mayura,
Good thinking but there is a major flaw in your solution. To make things easy to understand lets say
A's salary = x
B's = y
C's = z
Now according to what you said if each were to perform their operation as follows:
A adds x1 => x + x1
B multiplies y1 => y * y1
C subtracts z1 => z - z1
Now you say, each one reveal their result to all the others. So after round 1 each one know what the other's operated result was. Now, the average is computed as S/3 where S = x + x1 + y * y1 + z - z1
A will undo his operation and add his actual salary's average to the computed. So A will do
S/3 - (x+x1)/3 + x/3 = A1
Now again you say, he reveals this to others. The moment he does that the other can figure out what the salary of A was, right, as follows:
B can compute A's salary as
A1 - (y*y1)/3 - (z+z1)/3 = x
Since each knows what B's adjusted salary is and also they know what C's adjusted salary is.
So at the end of round 2, each one will know each's other salary. So the basic idea in this problem is how to get around the scheme of each one being able to compute each other's salary by what is being told. We cannot do any accounting for people who lie, for example if B and C scheme against A. So lets take a hypothetical situation, then you would need to make 'one small change' to your solution and it will work perfectly well. Think about it! Good thinking and you are almost there.
Let the 3 salaries be s1,s2,s3.
Let A choose a number N0. A adds his salary to N0 and gives the sum N0+s1 to B. B adds s2 to it and gives the sum N0+s1+s2 to C. Now C adds his salary and gives the sum s1+s2+s3+N0 to A. A subtracts N0 from it and gets (s1+s2+s3) and thereby the average.
Post a Comment
Subscribe to Post Comments [Atom]
<< Home