Story Version (scroll for TL;DR)
It's the end of the first quarter of 2017.
This means it's the end of the 2016 fiscal year (at least in my country it is).
It's time to draw the line.
So the CEO did his calculations and said we did a good job so we should get a bonus.
Yippeee...
But there is a catch. Or two.
The CEO values smart people more than hard working people.
So here is his bonus scheme straight from the CEO's mouth.
You all know your own monthly salary but not those of your colleagues.
If you can guess how much it costs me to pay all of you in one month you get a bonus. Otherwise I'll just take you out for beers, but no bonus.
You cannot ask the financial department. And you cannot find out how much the other people make a month.
Now what strategy should we apply in order to know the total sum of the salaries per month? I really want the bonus.
All I can tell you is that we are at least 3 employees and you can ignore the tax calculations.
Note: This is just a story. It didn't actually happen... because there are no bonuses.
TL;DR
Each of N people know a number but don't know the number the others know.
How can the people find the sum of those numbers without finding out each other number? $N >= 3$
Answer
Here's my solution:
Employee 1 takes a slip of paper and writes a random number X on it in pencil. He passes it to Employee 2, who erases X and writes the sum of his salary and X - let's call this value Y. Employee 2 passes the paper to Employee 3, who does not know the initial value of X and thus cannot know what Employee 2's salary was. Employee 3 adds his salary to Y, erases the old Y, and writes the new one down.
This process is repeated until Employee n has added his salary to Y, whereupon he passes the paper back to Employee 1. Employee 1 adds his own salary to Y, then takes away X, and is left with the cumulative total of all the employee's salaries. At no point does any employee know any other employee's salary - only the cumulative total so far, plus X.
No comments:
Post a Comment