# Salary sum with a twist

You've been considering your boss' offer, when you decide to try and sort things out for yourself.

So, armed with your thought reading device, you set out to find the total salary of all the employees.

However, your boss isn't thinking about the total salary; instead, they are thinking of a special twist. If some group of employees manage to work out the salary of a different employee, they all get double the bonus and the revealed employee gets none.

Unfortunately, none of the team really like you. Maybe it's something to do with how you play online games instead of going to team meetings?

You know that the rest of your team will collaborate and do anything possible to find out your salary once your boss reveals the twist (though they will not reveal their own salary in case someone rushes off and claims the double bonus for themselves). So you need to find a strategy to put before them to work out the total sum of the salaries so they can't find your salary without giving their salary away (both directly and indirectly).

Luckily, you are known as the most rational member of the team, so they will listen to any strategy you put forth as long as it doesn't reveal any individual salaries (without collaboration)

## Is this even possible? For all numbers of team members? If not, which numbers?

Disclaimer: I don't know the answer to the questions

## TL;DR

• Find a strategy to find the total sum of the team members.
• The other members of your team must not be able to find your salary with collaboration and so everyone knows, without some subgroup being able to work out the salary of someone outside that subgroup who is not you with collaboration.
• There are at least three members in the team including you.

Notes:

• No electronics are allowed in your strategy
• If you want your coworkers to like you more, you could sacrifice the bonus to them. – Ian MacDonald Apr 12 '17 at 12:36
• How could it be possible for the most rational employee to not be well liked by everyone? Oh wait, I guess that's pretty normal. – user3294068 Apr 12 '17 at 15:11
• I think you have awarded the tick too soon. There are many other possible strategies. – Dr Xorile Apr 13 '17 at 14:22
• @DrXorile There are many possible strategies, yes, but the strategy-stealing argument shows that whatever strategy you have will succeed/fail under the conditions mentioned in the accepted answer. – boboquack Apr 13 '17 at 22:37
• It's a clever argument. I just don't think it applies. The situation of n players does not necessarily reduce to n-1 players, because you are the strategist and can reveal information. Specifically, n=4 could be handled to reveal information that made it unsafe for the 3 remaining players to figure out their salary sum, because that would allow further deductions to be made. – Dr Xorile Apr 14 '17 at 2:56

I think for n=3

the "standard" approach works.

That is,

you (A) pick a random number, pass it to B, B passes random+B_salary to C, C passes random+B_salary+C_salary to A, A can then work out the sum. But in fact what I really want to say is that any approach that works for the original problem also works for this one when n=3.

Because

if B and C work out your salary, then they also know the sum of their salaries, and hence they also know one another's salaries.

When n=4

the problem (for you) is insoluble, because if you have a way of finding A+B+C+D then B,C,D can now do the n=3 case as above, at which point they know B+C+D as well as A+B+C+D and so they can deduce your salary.

• I think you can generalize this to a complete description of when it's possible and when it's not. – histocrat Apr 12 '17 at 13:23
• Doesn't your answer for n=4 apply to all n>4 as well? If all the other employees collaborate, they can always find out your salary once the total salary becomes public knowledge. Hmm, it's not clear from the puzzle statement if the total salary will become public knowledge though, only that you have to find it out. – Jaap Scherphuis Apr 12 '17 at 14:25
• +1 If n participant finds the result of f(n)=sum(1,..,n) then n-1 can find result of the f(n-1), which then can computed by f(n)-f(n-1) that gives away the salary of the employee – shyos Apr 12 '17 at 14:41
• It might turn out that the only ways for the others to collaborate (so as to find out the sum of their salaries and hence your salary) have the consequence of potentially revealing some other salary within the group. – Gareth McCaughan Apr 12 '17 at 14:46
• If I'm not mistaken: if n participants find the result f(n) = sum(1,...n) then n-1 can find f(n-1). However! All of the participants 1,...,n-1 are at risk that a smaller group of n-2 participants finds a sum of n-2 salaries, from which they can deduce the excluded participant's salary, which means any of the n-1 participants could potentially lose their bonus. This suggests that they won't try to find the f(n-1) sum because of the threat of no extra socks for christmas. – Piotr Pytlik Apr 12 '17 at 15:17

If nobody trusts anybody, then the puzzle is solvable for

All odd $n \geq 3$, but no even $n$

Because.

As Gareth pointed out, for $n=2$, if either party knows the sum of their salaries, then she also knows the other person's salary, since she knows her own. Thus, we can use any established strategy for $n=3$ and nobody can safely deduce my salary, since that would put them into the $n=2$ case, and they would be revealing their own salary to their coworker.

Extending.

Again, as Gareth pointed out, this is not solvable for $n=4$ because if you do, then your three coworkers can safely work out their own salary total and thus deduce yours. This therefore means that any strategy works for $n=5$, since anyone trying to deduce your salary would put themselves into a position where their own salary would be revealed, as well. This pattern would extend: the problem is solvable for all odd $n \geq 3$ and unsolvable for all even $n$.

Conversely, if everybody except you trusts everybody else except you, and you're the lone disliked employee,

Then you are doomed for any $n>3$. They would all collaborate to learn your salary and you'd be screwed. You're still safe for $n=3$ because two people cannot collude to learn the sum of their salaries without intentionally revealing their own salary, which is not allowed.

• Still reading your answer, but i think you might've rendered my answer void... :( – Piotr Pytlik Apr 12 '17 at 15:28
• I do not think this is correct. As the chief strategist you are free to publicise other information en route to the sum of all salaries. I believe that if you publish more information in addition to the sum of all salaries you can create a situation where revealing your salary will automatically reveal someone else's salary. Per my comment in Gareth's answer, I think this is then doable for $n\geq 6$. – Dr Xorile Apr 13 '17 at 1:58
• Yes... under assumption you and they keep just the same basic strategy. For N=5 they can make a group of 3 people who tells the sum to 4th, who then knows your salary (but cannot tell it loud without exposing his to the other 3). For N=6 you can make 2 groups of 3 people... – Zizy Archer Apr 13 '17 at 7:44
• Depends on what method you use to sum salaries. If you use the traditional method that Gareth mentions, than two of your coworkers (your "neighbors") can collude to steal your salary. 2 knows what the random number is and N knows what the (sum - your salary + random number) is. – jousle Apr 13 '17 at 15:21

For N=3 and N=4, this has been sufficiently solved by Gareth. But for other numbers there are additional strategies you or they can use beyond the trivial ones.

I assumed you can loudly tell multiple sums and they will cooperate with that, unless their own salary could be deduced by that. Then they make their own sums which they tell just among themselves.

You are a person X and the others are A, B ...

N=5:

You cannot make a group of 3 yourself, as the 2 people not in the group will know each other's salary. So you need a single large group.
They will make a group of 4 and figure out your salary.

N=6 and onwards:

Make a group X, A, B. Whatever strategy they attempt to use will lead to A knowing B's salary and vice versa.

• To answer your questions: they all cooperate as long as their own salary can't be discovered. All of them must also safely know my salary. – boboquack Apr 14 '17 at 3:15

Everyone's logic for this being impossible makes sense, but is still wrong. They forgot one key point, Juding from the other situation's you've been part of it sounds like your a selfish bastard willing to cheat or screw over his coworkers to get what you want. That always makes things so much easier...

In fact a Selfish bastards deserver twice the bonus after all don't they!? Why settle for the bonus when we can figure out ever one else's salary as well? sure it means the rest of your coworkers won't make any money, but they deserved it for being tempted to cheat you just becaues your a selfish bastard so it's all fair...right?

Assuming you have N employees you will get N slips of paper, already pre folded so no one can read their content. You explain to the team that these slips of paper each have a single number from 1 to N written on it, with no duplicate numbers. You will throughly shuffle the papers and then each person will randomly take one slip.

Each person then tells everyone what what their salary plus the value on the paper is, perhaps writing it down on a message board. Since no one knows what the value on each persons paper is they can not deduce anyone's salary from knowing what the salary + slip value is. Once every person provides a value you add up all these numbers and subtract the combined value of all the numbers on your slips of paper your be left with the combined salary.

You justify this by saying it prevents anyone from colaborating to calculate anyone else's salary. If you use the sequential approach then the Xth person's salary could be calculated by person X+1 tell person X-1 what value person X wrote, (or any number of similar consparicies). It only takes two to three people working together to harm someone which is too much of a risk. But with the paralized approach there is no way to calculate any one person's salary unless every other person on the team colaborated together to screw that poor singler person over, and surely you can be confident the entire office would never all conspire together just to cheat one per person right!?

(you may need to use values larger then 1 to avoid hurting anyone's ego by giving away too close an estimate to their real salary, but you get the basic idea here)

Of course what your coworkers don't know is that you have actually written the same value on every slip of paper, say N/2, and also lied about your own salary value.

Since you will lie about your own salary in this calculation even though the rest of the team collaborates against you they will fail to calculate your salary. Meanwhile since you know how much each person added to their own salary you can correctly calculate every person's salary. Ask the boss if instead of doubling your bonus for calculating one person's salary if you can get an increase to your bonus for every team member who's salary you correclty guess, you could be pretty rich..

Of course there is a slight chance your fellow employees may not be 100% happy with this result. You may not want to eat or drink anything left unsupervised near a coworker after this, but that's the peril of being a selfish bastard.

EDIT:

If you want to play nice and have your team like you there is another solution that actually makes you more money and earns good will from the team, if you trust them to cooperate. You could simply tell the team your salary! Everyone on the team earns double the bonus this way. However, in exchange each person on the team agree's to give you a percentage of their bonus, say 2/3 of the base bonus value. Now with just 3 other teammates you teammates will each earn 2 - 2/3 = 4/3 of the bonus thanks yout your help, while you will earn 0 + 3 (2/3) = double the bonus after each person gives you part of their bonus. You each earn more money then if you all colaborated to earn just the base bonus. With more employeees you can ask for a smaller donation while still earning even more. Since the most you could earn from cheating your employees was twice the bonus amount this approach could be more profitable if you trust your employees.

And who said I can't pretend the lateral-thinking tag was on any puzzle I please!? :)

I'm leeching a bit off of Gareth's answer, but only to add the n>4 case.