Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

You should be able to solve this.

Name: Anonymous 2009-09-13 21:54

A group of jealous professors is locked up in
a room. There is nothing else in the room but pencils
and one tiny scrap of paper per person. The profes-
sors want to determine their average (mean, not me-
dian) salary so that each one can gloat or grieve over
his or her personal situation compared to their peers.
However, they are secretive people, and do not want to
give away any personal salary information to anyone
else. Can they determine the average salary in such a
way that no professor can discover any fact about the
salary of anyone but herself? For example, even facts
such as "three people earn more than $40,000" or "no
one earns more than $90,000" are not allowed.

Name: Anonymous 2009-09-14 18:34

Why am I doing your discrete homework for you? Ah well.

Let's rephrase the requirement to be no n-2 or less professors can know the salaries of any other professors in a group of n.

The setup:
Have the professors decide on a number m that the average of the salaries will be less than. If they bitch about how discussing that m might reveal too much, take an assload of primes, repeat the following procedure a bunch of times, and then use Chinese Remainder Theorem.

The procedure:
Everyone but one dude takes their piece of paper and writes down a number between 1 and m. This one dude adds up all of the numbers mod m, and puts the additive inverse of their sum on his paper. The papers go in a hat. Everyone takes a number, adds their salary to it, and then rips off and eats the original number. They add all of their numbers together, and they will get the sum of their salary mod m. Given appropriate assumptions about the total sum of every salary, their average salary should be fairly simple to find.

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List