Average Salaries 2

Back in Average Salaries 1, 12 employees came up with a method to find out their average salary without revealing their individual salaries to anyone. Here’s the method they came up with:

Spoiler: Solution to the previous puzzle

Number the employees them 1 to 12.
Employee 1 comes up with a random number, which we will call $X$ , and adds his salary to it. He emails this sum to employee 2.
Employee 2 adds his salary to the sum and emails the new sum to employee 3.
Employee 3 does the same, sending the new sum to employee 4.
Repeat this process until employee 12 has everyone’s salaries + $X$ . He then sends this overall sum to employee 1.
Employee 1 now has the overall sum, which is the sum of everyone’s salaries + $X$ . He subtracts $X$ from it, leaving him with the sum of all their salaries. He then divides this sum by 12 to get their average salary.

However, before they begin, one employee interrupts. “Wait! I’m number 7. What if number 6 and number 8 collude? Employee 6 can tell employee 8 what he sent me, then employee 8 can calculate the difference to get my salary.”

The employees pause to think about it. With their current solution, if any 2 employees collude and reveal the contents of their emails, they can find out someone else’s salary. That’s not great.

Is there a way we can do better? Can we make it such that if any 10 employees try to collude, they still can’t get anyone’s salary?

Hint: Why 10 employees, not 11?

No matter what method you use to come up with the average salary, any 11 employees colluding can always get the 12th employees salary.

Let’s assume the 12 employees find out their average salary $S_{1}$ .

If any 11 employees are colluding, they can use the same method to find out their average salary $S_{2}$ .

Then the 12th employee’s salary is $12 S_{1} - 11 S_{2}$ . This is possible no matter what method you use to get the average salary.

Hint

Just as before, the number of coworkers doesn’t matter. In general, for $n$ employees, is there a method that doesn’t allow any $n - 2$ employees to get another employee’s salary?

Hint: Examining A Semi-Working Solution

After some more discusson in a video call, someone comes up with another solution. Instead of sending the email in a loop from 1 to 12, then back to 1, they will send it in 2 loops instead.

This time, every employee comes up with a random number that they’ll keep secret.

Number the employees them 1 to 12.
Employee 1 emails his salary and his random number to employee 2.
Employee 2 adds his salary and his random number to employee 1’s salary and emails the sum to employee 3.
Employee 3 does the same, sending the new sum to employee 4.
Repeat this process until employee 12 sends the sum back to employee 1.
This time, employee 1 deducts his random number from the sum and sends the new sum to employee 2.
Employee 2 deducts his random number and sends the new sum to employee 3.
This repeats until the sum reaches employee 12. Employee 12 deducts his random number, then divides the final sum by 12 to get the average salary.

Let $s_{i}$ be the $i^{th}$ employee’s salary, and $r_{i}$ be the $i^{th}$ employee’s random number. Our total sum would be:

$\sum_{i = 1}^{12} (s_{i} + r_{i}) - \sum_{i = 1}^{12} r_{i} = \sum_{i = 1}^{12} (s_{i})$

The final sum divided by 12 gives the average salary, as expected.

Employee 7 is not convinced. “Employee 6 and 8 can still figure out my salary! On both passes, they can see how much I’ve added and deducted. They can add the differences up to get my salary anyway.”

Back to the drawing board.

Solution

Let’s imagine a sequence of emails that goes through all the employees in some specified order. As before, each time an employee receives a cumulative sum, modifies it, then emails it on to the next employee.

The semi-working solution earlier certainly didn’t work, but there’s a seed of a solution in there. Let’s say for a particular employee X, the email chain passes through him three times.

The first time, employee A emails the sum to employee X. Employee X adds 1000 to the number and emails it to employee B.
The second time, employee C emails the sum to employee X. Employee X subtracts 2500 and emails it to employee D.
The third time, employee E emails the sum to employee X. Employee X adds 7000 and emails it to employee F.

The total sum of his changes amounts to his pay of $5500.

However, imagine that you’re another employee trying to get that previous employee’s salary. If you only got access to 1 or 2 of the numbers (1000, -2500, or 7000), you still don’t have any information as to that employee’s salary. You need all the numbers to compute the person’s salary.

In fact, you need access to employee A, B, C, D, E, and F to get all these numbers. If any one of them refuse to collude with you, you can’t determine employee X’s salary.

In general, for any employee X, all the employees that he sends and receives email from must be colluding in order to find out employee X’s salary. If any 1 of them doesn’t cooperate, then his salary remains unknown.

That gives us an idea of the strategy:

The email path must go through all the employees such that for any 2 employees X and Y, the email path must go through them.
For any employee X, all his contributions to the sum must add up to his salary. The individual contributions can be positive or negative.

But how do we determine what this path is? Let’s start with a scenario with 5 employees. Let’s represent it with a graph: each vertex represents an employee, and we draw edges between all pairs of employees. We want to draw a path that covers all edges.

In this example, we can traverse all the edges with the path:

1 → 2 → 3 → 4 → 5 → 1 → 3 → 5 → 2 → 4 → 1

This is called an Eulerian path: a path that traverses all the edges exactly once. The length of the path is $\frac{n (n - 1)}{2} = 10$ : the total number of edges.

:::note{type="info"}[Eulerian Graphs] If a graph has only vertex with even degrees, it must have an Eulerian circuit: a path that traverses every edge exactly once, ending on same vertex.

If a graph has exactly 2 vertices with odd degrees, it must have an Eulerian path: a path that traverses every edge exactly once. This path must start on one of the vertices with odd degrees, and end on the other vertex with odd degree. :::

However, this only applies to situations with an odd number of employees. How about when there are an even number of employees? Let’s take a look at a situation with 6 employees.

Here, we have 6 vertices of degree 5, which means there isn’t an Eulerian path. However, if we allow some pairs of employees to email each other more than once, we can add some repeated edges, marked in blue.

With our additional edges, we now have 4 vertices of degree 6, and 2 vertices of degree 5. We can start at employee 1 and end at employee 6. This is one of the possible Eulerian paths:

1 → 2 → 3 → 4 → 5 → 6 → 1 → 3 → 5 → 1 → 4 → 6 → 2 → 4 → 5 → 2 → 3 → 6

The length of the path is $\frac{n (n - 1)}{2} + \frac{(n - 2)}{2} = 17$ , where the second term accounts for the additional blue edges.

To summarise, the minimum length of this path (and thus the minimum number of emails sent) is given as:

{\begin{matrix} \frac{n (n - 1)}{2} & if n is even \\ \frac{n (n - 1)}{2} + \frac{(n - 2)}{2} & if n is odd \end{matrix}

For our situation with 12 employees, this will be our graph.

A valid Eulerian path would be:

1 → 2 → 3 → 1 → 4 → 2 → 3 → 4 → 5 → 1 → 6 → 2 → 5 → 3 → 6 → 4 → 5 → 6 → 7 → 1 → 8 → 2 → 7 → 3 → 8 → 4 → 7 → 5 → 8 → 6 → 7 → 8 → 9 → 1 → 10 → 2 → 9 → 3 → 10 → 4 → 9 → 5 → 10 → 6 → 9 → 7 → 10 → 8 → 9 → 10 → 11 → 1 → 12 → 2 → 11 → 3 → 12 → 4 → 11 → 5 → 12 → 6 → 11 → 7 → 12 → 8 → 11 → 9 → 12 → 10 → 11 → 12

The actual path is not important, but the optimal length of such a sequence is 71 emails.

With our valid email path, what each employee needs to do next is to see how many times they appear in the path, then split their salary into that many numbers.

Let’s use some examples.

Employee 4 shows up in the path 6 times. If he makes $4000, he can simply add 1000 to the sum each time it comes to him.

Employee 1 shows up in the path 5 times. If he makes $6200, he can:

Send 500 to the next person (since the path starts with him).
Add 7000 the second time the email comes to him.
Add 1234 the third time
Subtract 10,000 the fourth time
Add 7466 the final time.

If every employee does this, then the final sum at the end of the email path will be the sum of all employees’ salaries. They can divide this sum by 12 to get the average salary.

Previous puzzle in this series

Average Salaries 1

Try These Next

Equal Shape Cutting 4

Stack of Coins 2

Close Shave with a Train