33
$\begingroup$

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$

$\endgroup$
  • 4
    $\begingroup$ Can it be assumed coworkers want to cooperate, i.e. everybody gets a bonus? Or only the first person coming up with a number? (Because, of course, the answer would be: Everybody should throw X matches onto the table where X represents their monthly pay. then you count. Done. ;c) ) $\endgroup$ – BmyGuest Apr 11 '17 at 9:40
  • $\begingroup$ Everyone gets it or nobody does. So .... collaboration $\endgroup$ – Marius Apr 11 '17 at 9:42
  • 1
    $\begingroup$ So if we actually figure it out, that's not a guess... $\endgroup$ – aslum Apr 11 '17 at 19:12
  • 1
    $\begingroup$ i believe this is called en.wikipedia.org/wiki/Secure_multi-party_computation $\endgroup$ – shyos Apr 12 '17 at 14:25
  • 1
    $\begingroup$ This question showing up in the HNQ list is one of the few times the icon confusion between here and The Workplace matters. $\endgroup$ – Bobson Apr 14 '17 at 12:31

12 Answers 12

59
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ Yep, this is it. Thank you. I'll go grab my bonus now. $\endgroup$ – Marius Apr 11 '17 at 10:19
  • 2
    $\begingroup$ But you've found out how much "the other people" make a month! $\endgroup$ – Samthere Apr 11 '17 at 12:16
  • 2
    $\begingroup$ Collectively, yes. Individually, you have no idea how that's divided up between the previous people - and even then it would be off by X, and you don't know what X is unless you're Employee 1. $\endgroup$ – F1Krazy Apr 11 '17 at 12:19
  • 2
    $\begingroup$ That's why this strategy does not work with 2 employees. You can find out where you are relative to the average though. $\endgroup$ – Marius Apr 11 '17 at 12:54
  • 1
    $\begingroup$ @justhalf: I was about to reply that only one employee gets the prize. Then I realized that the original question did not specify whether only one employee wins or if everyone can win (by cooperating). $\endgroup$ – Ross Presser Apr 12 '17 at 17:58
25
$\begingroup$

The following works:

First employee picks a large random number and whispers it to the second. 2 adds her salary to it and whispers the result to the third. 3 does likewise, then 4 ... until finally the last employee adds his salary to the running total and whispers it to 1. Now 1 subtracts off the random number to get the sum of everyone else's salary, adds her own salary and tells the boss.

[EDITED to add: Be it known that F1Krazy's near-identical solution was posted just before, not just after, this one.]

$\endgroup$
  • $\begingroup$ The time difference between your answer and F1Krazy's is 1'30". I assume it took you that long to type. So you have my +1. No checkmark tough. $\endgroup$ – Marius Apr 11 '17 at 10:17
  • 1
    $\begingroup$ Yes, it took me more than a minute to type. I was on a mobile device. If I had to guess I'd say that F1Krazy and I probably started writing within seconds of one another :-). But indeed, I shouldn't get the checkmark, and the point of my edited addition about the order was to make sure I didn't. $\endgroup$ – Gareth McCaughan Apr 11 '17 at 10:33
15
$\begingroup$

This is how i would actually do it practically:

  • Get a calculator and some tape.
  • Tape the display shut
  • Each person types in his salary and presses +
  • The last one removes the tape and the sum is clearly visible

( Optimization: The third employee can already remove the tape, since he will only see the sum of the first two salaries. After he types in his own salary and presses + the display will then just show the overall sum and you can pass the calculator without the tape, so everyone has an easier time typing in their numbers )

$\endgroup$
  • 1
    $\begingroup$ Good approach. I forgot to add 'no-computers' tag on this :D $\endgroup$ – Marius Apr 11 '17 at 13:50
  • 5
    $\begingroup$ What if the + and '÷` keys have been switched, the calculator does no order of operations precedence, and it breaks on decimals - now how do you solve it? Paging Dave... $\endgroup$ – Rubio Apr 11 '17 at 13:58
  • $\begingroup$ @Rubio. I know this was supposed to be funny, and it is, but maybe you are on the right track for creating an awesome PSE question. $\endgroup$ – Marius Apr 11 '17 at 14:17
  • 5
    $\begingroup$ I'd do this, but repeat a decent number of times. If people can't see what they're putting in, they're gonna mess up sometimes! $\endgroup$ – Samthere Apr 11 '17 at 14:27
  • $\begingroup$ Why tape the display? $\endgroup$ – max8126 Apr 11 '17 at 15:28
14
$\begingroup$

My comment turned into an answer:

Everybody secretly throws X things into a bag, where X represents their accurate monthly payment, and 'things' is something small like a matchstick or the like. Then you just count the itmes when all are done.

Why is it different/superior ?

- Does not require that anybody gets to know the payment of anybody else
- Does not require any sequence

Why is in inferior ?

- requires 'things' - although writing numbers (or representive 'dots') on a piece of paper can simplify this
- These 'things' must be sufficiently low-value to allow for the precision of everybody's salary - Can be improved by a) first agreeing that each individual salary is a multiple of X and then use X, b) Using dots & dashes on a piece of paper (not number, as dots & dashes will not identify personal handwriting)

Is it a valid answer?

I think yes, for the puzzle as stated. But then, I think the puzzle is not really very "puzzling" as stated, but rather a trivial question. You're not allowed to ask financial department soo.... just ask somebody else for the total (or put it togehter.)

$\endgroup$
  • $\begingroup$ This works, You have my +1, but the pitfall is that it requires a lot of things. And it's not that elegant. $\endgroup$ – Marius Apr 11 '17 at 10:13
  • $\begingroup$ Yes, I also think it's inferior to F1Krazy's (which I upvoted for that reason.) $\endgroup$ – BmyGuest Apr 11 '17 at 10:14
  • 1
    $\begingroup$ You can avoid the "inferior" part by using e.g. pieces of paper with values of 10^N (N>0) written on them. Have them throw the appropriate number of these pieces in the bag along with a handwritten piece that contains the leftover amount. $\endgroup$ – slvrbld Apr 11 '17 at 14:45
  • $\begingroup$ @slvrbld: then the handwriting will reveal who has that specific leftover amount =D $\endgroup$ – justhalf Apr 13 '17 at 0:31
  • $\begingroup$ This is an ingenious solution! Together with slvrbld we can make it more practical by using Monopoly money and just throw it inside a bag. $\endgroup$ – justhalf Apr 13 '17 at 0:32
7
$\begingroup$

This is somewhat of a muddle of BmyGuest’s answer and the F1Krazy/Gareth McCaughan answer:

Take $2N$ pieces of paper; give two to each person.  Each person chooses a random number $R_i$ and writes it on one piece of paper, writes $Salary_i-R_i$ on the second piece of paper, and throws both pieces of paper into a hat.
Dump them out and add the numbers; the sum is $\sum_{i=1}^NSalary_i$.
People can see all $2N$ numbers without being able to derive any individual salary value.

If you want the average, divide by $N$.

Reality check:

The pieces of paper should be made as identical as possible; i.e., the same size, drawn from the same source (or cut from the same source).  All participants should use the same writing instrument and should strive to print neatly and uniformly, avoiding distinctive handwriting.

$\endgroup$
4
$\begingroup$

Edit: If there is only one try.

Inspired by Citadel character distribution.
I write on N papers - 1 to N number.
I give each paper randomly to each person.
Everyone say salary+number on paper.
I sum everything and take off (1+2+..N)

$\endgroup$
  • $\begingroup$ I like that for creativity. Still think F1Krazy's is more straight forward and practical though. In particular if there are a lot of employee's. +1 though. $\endgroup$ – BmyGuest Apr 11 '17 at 10:17
  • $\begingroup$ This allows people to know approximately other people's salary. $\endgroup$ – Scott Apr 12 '17 at 2:10
4
$\begingroup$

Slightly similar to some of the answers.

Have everyone add a random number to their salary. Give that result to a certain person to add up. And give the random numbers to another person to added up. Subtract the totals from each other and that will be the sum of all the salaries.

$\endgroup$
  • $\begingroup$ Can you put your answer in spoilers (>! at the start of each line)? Thanks! $\endgroup$ – boboquack Apr 12 '17 at 9:25
1
$\begingroup$

Assuming everyone gets to hear every guess, and that only one person needs to be correct for everyone to get a bonus:

Each employee makes a 'guess' of their own salary, plus the running total of those before.
So for 3 employees, respectively earning 10 currency, 15 currency, and 12 currency, employee one says 10. Employee 2 says 25. Employee 3 says 37, thus earning a bonus.

$\endgroup$
  • $\begingroup$ I like it, but it has the inbuilt assumption that everybody guesses alound and in order. Not much different than my (see comments) assumption that everybody can just "chip in" and then there is a count (which does not require a sequence or anybody knowing anybody elses pay, if it should remain secret.) $\endgroup$ – BmyGuest Apr 11 '17 at 9:42
  • $\begingroup$ Isn't "And you cannot find out how much the other people make a month." spoiling it? (First salary needs to be known exactly by everyone.) @F1Krazy's is doing better (and less clumsy than my own answer.) $\endgroup$ – BmyGuest Apr 11 '17 at 10:05
  • 2
    $\begingroup$ If the first one yells out his earning, everyone will know it. If the second one adds his earnings to the first one's (which everyone knows already) everyone will find out the exact amount the second one earns. It contradicts the requirement. $\endgroup$ – Marius Apr 11 '17 at 10:16
1
$\begingroup$

It boils down to obfuscating the salaries by either directly adding up the salaries in a way that they all "drown out"/aren't seen at all (like the "adding things" or calculator method), or changing them with controlled randomness involved (but so that none of them can figure out the way the other salaries must have been adjusted through the process of elimination).

First, they take $N$ pieces of paper, write down a distinct number from 1 to $N$ on each and put them into a pot. Then they randomly pick a number, with the one picking 1 subtracting a certain number $X$ known to everyone from his/her salary and the one with 2 adding $2X$. Everyone else adds $X$. They all write down the results. That way the sum can be worked out, but no one knows how much which one of the others has added or subtracted.

$\endgroup$
  • $\begingroup$ This is unclear.  For starters, the role of the $N$ pieces of paper: are they only to put the people into a random order?  If so, you’re writing too many words: just say “the people choose a random order”.  You should say more words about what $X$ is, where it comes from, and, most importantly, how the process ends.   … (Cont’d) $\endgroup$ – Peregrine Rook Apr 14 '17 at 19:13
  • $\begingroup$ (Cont’d) …  I guess you’re saying that they have another $N$ pieces of paper.  Person 1 writes down $Paper_1=Salary_1-X$, Person 2 writes down $Paper_2=Salary_2+2X$, and everybody else writes down $Paper_i=Salary_i+X$.  They collect the papers, add the numbers, and compute $\sum_{i=1}^NSalary_i~=~(\sum_{i=1}^NPaper_i)~-~(N-1)X$.  This seems complicated.  … … … … … … … … …  P.S. Maybe I’m just being dense today, but I don’t understand why the original version of this answer wouldn’t work for $N=3$. $\endgroup$ – Peregrine Rook Apr 14 '17 at 19:13
  • $\begingroup$ $X$ is just an arbitrary value. Let everyone know it and you're good to go. As for the papers, it doesn't matter if the writing order of the numbers is random or not. They just write the numbers from 1 to $N$, and then randomly pick them from a pot. The initial answer wouldn't apply if $N=3$, because one would add the already-known $X$ and the other two would subtract $X$, allowing the former to be sure that both of them must have subtracted $X$. He wouldn't really know which result belongs to whom, but I thought deducing any actual salary amount could be forbidden. $\endgroup$ – Nautilus Apr 14 '17 at 19:46
1
$\begingroup$

Assuming you're in no huge rush.

Have everyone get together and state their number, get someone good at maths to add it up.

But first, to anonymise it:

Allow people time to 'give' some of their number to remember to other people. So if I have to have a salary of 100, and you have 200, I could give you 20, meaning I now remember 80 and you remember 220 (note, not giving away actual salary, just the remembering of it).

To keep people from getting some information,

Do this in a way that people cannot necessarily see whom is transferring money with whom - knowing that you are the first person to trade with someone establishes a lower bound on their salary. If they give you X, their salary must be at least x if you are sure they have not been given salary from anyone else. This could be done by having an assigned, private area for each person to wait in when not out seeking a trade.

Keep repeating this process for a sufficient amount of time.

Sufficient will be based on a few things - we want to give people enough time to feasibly give away their whole salary, in increments that do not give any information away (starting no larger than minimum wage, but then doubling each x minutes, where x is the amount of time it takes to walk over and set up a trade), whilst also having enough time to be 'in their office' to receive a roughly equal number of trades.

This is similar to other 'random number generator' proposals above, but it mitigates one flaw I see with these. To explain this, name a color and a tool.

If you said red hammer, you've just demonstrated how bad humans are at picking 'randomly'. The added complexity of my proposal is there to limit the damage that could be done by people being bad at choosing random numbers.

$\endgroup$
  • $\begingroup$ This seems to be very closely related to F1Krazy’s answer, a.k.a. Gareth McCaughan’s answer: Person 1 chooses a random number $X$ and tells it to Person 2, who adds it to his salary.  When the sum gets back to Person 1, he adds his salary and subtracts $X$.  … … … … … … … … … … … … … … … … … … … … …  How can you tell when you’ve done this process long enough to have anonymized/obfuscated the individual salaries “enough”? $\endgroup$ – Peregrine Rook Apr 12 '17 at 5:23
  • $\begingroup$ Thanks for pointing those out.The answers to both made sense in my head, but wouldn't have been clear to anyone else. $\endgroup$ – Scott Apr 12 '17 at 23:43
0
$\begingroup$

Just get a random person to hear and add the totals, then report the total to everyone. No one is the wiser regarding salaries and everyone gets the bonus. No computers involved. Keep It Simple Stupid.

$\endgroup$
  • 2
    $\begingroup$ The random person is the wiser, unfortunately. $\endgroup$ – boboquack Apr 11 '17 at 22:40
  • $\begingroup$ then the random person will know all the salaries. Not good. $\endgroup$ – Marius Apr 12 '17 at 6:34
  • $\begingroup$ I think this is a nice answer, if we have trusted third party. $\endgroup$ – shyos Apr 12 '17 at 14:22
  • $\begingroup$ If you are suggesting this third party isn't part of the group, I think this fits in the spirit of "you can't ask the financial department". $\endgroup$ – Ian MacDonald Apr 12 '17 at 19:42
0
$\begingroup$

Take a small bag, everyone has to put 2 papers in it :

  • 1 paper with a higher random number added to their salary
  • 1 paper with this random number written as negative

So let's say Bob makes 100K, he randomly chooses 140K.

He puts a paper written 140K and an other one written -40K (140K-40K = 100K, his salary).

Once everyone added their 2 papers in the bag, shake the bag and just make the sum.

$\endgroup$
  • $\begingroup$ Why do you even beed the random negative amount? $\endgroup$ – Marius Apr 12 '17 at 14:31
  • $\begingroup$ How would you know how much have been added to the real sum then? You need to remove the added amount, to get the real sum. Since the papers are independent, you don't know which number subtracts which one, so it's impossible to find anyone's real salary. $\endgroup$ – toto Apr 12 '17 at 14:33
  • $\begingroup$ Full example with Bob, Alice and Paul. Bob makes 70K, Alice 80K, Paul 90K. Total = 240K (that's what you wanna know). Bob chooses 130K, so he puts a paper 130K and -60K (130-60=70K). Alice chooses 100K, so shes puts 100K and -20K. Paul chooses 130K, so 130K and -40K. Total = 130+130+100-60-40-20 = 240K. Now if Bob is trying to find Alice' salary : He put 130K and -60K. So for him, Alice salary is 130-20 (110) or 130-40 (90) or 100-20 (80) or 100-40 (60). Basically Bob wouldn't know Alice's real salary. $\endgroup$ – toto Apr 12 '17 at 14:44
  • $\begingroup$ Then why can't bob alice and paul throw in the bag papers with their real earnings? Why do they need to add something and then subtract it. I am not saying you are wrong. You are just over engeniering it. $\endgroup$ – Marius Apr 12 '17 at 14:48
  • $\begingroup$ If the papers are recovered afterwards, it does give away some information on the salaries. For example, with 5 other employees, you can work out the $5^2$ possible salary values they can have. If the chosen random numbers are quite wide ranging, several combinations will be ruled out (due to negative or very low salaries). So some information is leaked, but probably not enough to recover the actual salaries, and there is no way to match those values to particular people even if you can guess the ranking. $\endgroup$ – Jaap Scherphuis Apr 12 '17 at 14:52

protected by Zyerah Apr 12 '17 at 15:38

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.