35

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

bobble
  • 10,245
  • 4
  • 32
  • 80
Marius
  • 18,049
  • 4
  • 54
  • 101

12 Answers12

62

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.

F1Krazy
  • 8,048
  • 1
  • 33
  • 62
  • 4
    Yep, this is it. Thank you. I'll go grab my bonus now. – Marius Apr 11 '17 at 10:19
  • 2
    But you've found out how much "the other people" make a month! – Samthere Apr 11 '17 at 12:16
  • 2
    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. – F1Krazy Apr 11 '17 at 12:19
  • @F1Krazy 2 knows X but not the total sum. – Mindwin Remember Monica Apr 11 '17 at 12:34
  • 2
    That's why this strategy does not work with 2 employees. You can find out where you are relative to the average though. – Marius Apr 11 '17 at 12:54
  • @F1Krazy Not a complaint about your answer, just in the phrasing of the question it's not definitively clear to me that not being allowed to know what other people means "not allowed to know what any one person makes". Not a real issue :P – Samthere Apr 11 '17 at 14:20
  • But Marius, your post specifically states $N >= 3$, so it doesn't have to work for two employees. – Ian MacDonald Apr 11 '17 at 15:52
  • @IanMacDonald. Yes it is true. I was just trying to explain why the min 3 condition was needed. – Marius Apr 11 '17 at 17:20
  • There is no incentive for anyone to cooperate with this scheme, since only employee 1 gets the answer. – Ross Presser Apr 11 '17 at 21:22
  • @Samthere:  The question says, “You all [each] know your own … salary ….  If you can guess how much it costs me to pay all of you …”.  So it’s quite clear that person who solves the challenge will be trivially able to compute $\rm Salary(others)=Salary(total)-Salary(self)$. – Peregrine Rook Apr 12 '17 at 00:46
  • @Peregrine_Rook only under the assumption that it's possible to guarantee an exact answer, and that a person has to know the number they submit. You could have a puzzle without those. – Samthere Apr 12 '17 at 01:38
  • @RossPresser: The final sum can be broadcast to everyone with no one knowing any other's salary. – justhalf Apr 12 '17 at 03:20
  • 1
    @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). – Ross Presser Apr 12 '17 at 17:58
  • @RossPresser: Ah, fair point. I have always assumed that it is a cooperative thing, since the story talks about "we", and the last question uses "the people". – justhalf Apr 13 '17 at 00:29
  • @RossPresser That's why I asked this in the comments right away, and Marius clarified it. – BmyGuest Apr 13 '17 at 09:29
  • @BmyGuest Sorry, I missed both your comment and Marius's answer. I wish the question had been edited to clarify it there. – Ross Presser Apr 13 '17 at 14:33
25

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.]

Gareth McCaughan
  • 119,120
  • 7
  • 313
  • 454
  • 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. – Marius Apr 11 '17 at 10:17
  • 1
    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. – Gareth McCaughan Apr 11 '17 at 10:33
17

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

melfnt
  • 5,132
  • 2
  • 13
  • 58
Falco
  • 2,201
  • 12
  • 14
  • 1
    Good approach. I forgot to add 'no-computers' tag on this :D – Marius Apr 11 '17 at 13:50
  • 5
    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... – Rubio Apr 11 '17 at 13:58
  • @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. – Marius Apr 11 '17 at 14:17
  • 5
    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! – Samthere Apr 11 '17 at 14:27
  • Why tape the display? – max8126 Apr 11 '17 at 15:28
  • @max8126 Since the second employee could see the number of the first one on the display before he starts typing. And he can see the sum after pressing the + sign, and since he knows his own salary he can deduct the first employees salary from this. But you could remove the tape after the second employee, since the display will then only display the running total after pressing + – Falco Apr 12 '17 at 08:49
  • @Falco I see. Well you can have the first person start with a make-believe number, and when everyone is done, have him/her adjust that final sum by subtracting the fake number and adding the real number. Better yet, just tell the 2nd person that's what the first person is doing without actually doing it. – max8126 Apr 12 '17 at 16:25
  • @max8126 that is a great answer on its own, without using any tape – Falco Dec 02 '20 at 08:17
14

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.)

BmyGuest
  • 18,141
  • 1
  • 69
  • 147
  • This works, You have my +1, but the pitfall is that it requires a lot of things. And it's not that elegant. – Marius Apr 11 '17 at 10:13
  • Yes, I also think it's inferior to F1Krazy's (which I upvoted for that reason.) – BmyGuest Apr 11 '17 at 10:14
  • 1
    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. – slvrbld Apr 11 '17 at 14:45
  • @slvrbld: then the handwriting will reveal who has that specific leftover amount =D – justhalf Apr 13 '17 at 00:31
  • 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. – justhalf Apr 13 '17 at 00:32
7

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.

Peregrine Rook
  • 4,880
  • 2
  • 26
  • 40
4

Edit: If there is only one try.

Inspired by Citadels 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)

melfnt
  • 5,132
  • 2
  • 13
  • 58
Jan Ivan
  • 5,196
  • 14
  • 31
  • 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. – BmyGuest Apr 11 '17 at 10:17
  • This allows people to know approximately other people's salary. – Scott Apr 12 '17 at 02:10
4

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.

boboquack
  • 21,982
  • 1
  • 66
  • 138
five6
  • 41
  • 2
1

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.

LowIntHighCha
  • 8,596
  • 26
  • 50
  • 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.) – BmyGuest Apr 11 '17 at 09:42
  • 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.) – BmyGuest Apr 11 '17 at 10:05
  • 2
    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. – Marius Apr 11 '17 at 10:16
1

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.

Scott
  • 2,087
  • 12
  • 13
  • 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”? – Peregrine Rook Apr 12 '17 at 05:23
  • Thanks for pointing those out.The answers to both made sense in my head, but wouldn't have been clear to anyone else. – Scott Apr 12 '17 at 23:43
1

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.

Nautilus
  • 6,534
  • 10
  • 32
  • 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) – Peregrine Rook Apr 14 '17 at 19:13
  • (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$. – Peregrine Rook Apr 14 '17 at 19:13
  • $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. – Nautilus Apr 14 '17 at 19:46
0

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.

john
  • 11
0

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.

melfnt
  • 5,132
  • 2
  • 13
  • 58
toto
  • 821
  • 5
  • 16
  • Why do you even beed the random negative amount? – Marius Apr 12 '17 at 14:31
  • 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. – toto Apr 12 '17 at 14:33
  • 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.

     – toto Apr 12 '17 at 14:44
  • 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. – Marius Apr 12 '17 at 14:48
  • 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. – Jaap Scherphuis Apr 12 '17 at 14:52
  • 1
    If you directly throw the real salaries, you know that each number written is a salary. With the 'salt' (random number added), you don't know any salary amount. In my example with Alice, you have four numbers 110, 90, 80, 60, half of them are not actual salaries in the company. – toto Apr 18 '17 at 13:01