Last week, I posed this challenge: You and nine of your coworkers are sitting in a conference room when somebody wonders aloud about the group’s average salary. Everyone is curious, but nobody feels comfortable sharing their own pay with the group. How can you all learn your average salary without anybody learning any more information about another person’s salary (other than what can be deduced from the group average)? You all have pen and paper and can conceal what you write from others, but you have no other tools at your disposal. You may assume that everybody cooperates with the chosen strategy.
Solution to Puzzle #23: Money Secrets
Number the ten people from 1 to 10. Person one thinks of a random number. It can be positive or negative, but should be large in magnitude. Call the random number r, and the salaries s1, s2, …, s10. Person one adds their personal salary to their chosen number (r + s1), writes down the result, and slides it upside down to person two.
Notice that by looking at the result of r + s1, person two learns nothing about person one’s salary. If they received some random-looking negative 37-digit number, how could they deduce what part of it is r and what part is s1?
Person two then adds their salary to the number they received from person one (yielding r + s1 + s2), writes down the result, and slides it face down to person three. Again, person three learns nothing about the previous salaries. They didn’t see r + s1, they only see r + s1 + s2, which looks just as random to them as r itself would.
This process continues around the circle until the paper returns to person one, now containing r + s1 + s2 + s3 + s4 + s5 + s6 + s7 + s8 + s9 + s10.
Person one then subtracts r from the total, yielding just the sum of everybody’s salaries. They divide this by ten and report the average to the group.
Random numbers play an essential role in digital security and privacy in much the same way that they do in this puzzle. Randomly generated numbers can obscure sensitive information in sophisticated ways and allow researchers to rigorously prove properties of their data-protection systems.
I enjoyed reading your creative solutions to this puzzle. There were several variations that I hadn’t considered before. If you’re interested in alternative methods, I encourage you to read last week’s comments!
