ovi12 wrote:Vinyanenya wrote:
This is probably possible or impossible depending on how we define the words "any" and "fact", as well as the sample space of the professors' salaries. For example, if salaries are required to be strictly positive, then knowing the average salary x means that you know that no professor's salary can be larger than 2nx. I'm guessing that the intended solution is somewhere along the lines of:
[spoiler]The professors arrange themselves in a circle. One of them takes their salary, select some arbitrary number in secret, and adds it to their salary, then writes it down and passes their paper to the next professor. The next professor picks a secret number, then writes the sum of the number they received, their salary, and their secret number on their paper, then passes it down. This continues until the process reaches the first professor, who subtracts their secret number from the total, writes that number on the unused side of their paper, and passes the piece of paper down. Every professor in turn subtracts their secret number from the number they received until everyone's done so, at which point the last professor wrote down the total sum of their salaries.[/spoiler]
My solution had the same idea, but now that I read Humman's answer I think he is the correct one. There are two reasons:
1) Since whatever the method they would all know the average at the end, so they would know no professor makes more than the average * n. This contradicts the last sentence in the riddle. But the last sentence in the riddle explicitly forbids them knowing such an information. This problem is from a very good math book, and this is too a contradiction for the author to not have caught (sadly I didn't catch it).
2) Being a math book, it is proof-oriented. The idea of getting them in a circle and plus minus a random number is good, but I have no idea how you would go about proving that they cannot derive any information whatsoever (I'd actually be very interested if you knew how) from performing this proccess. Therefore I think Humann's answer is correct, because it is a proof that it's impossible.
This question is actually way deeper than I expected so I'll have to get back to you on whether or not it's actually possible. Essentially, every professor has a salary represented by some random variable X_i and can generate their own random variable Y_i. On the first pass through, the first professor does some sort of transformation Z_1 = f_1(X_1, Y_1), and in general, the ith professor does a transformation Z_i = f_i(Z_{i-1}, X_i, Y_i). On the second pass, the first professor does some transformation g_1(Z_n, X_1, Y_1) = Q_1 and in general everyone does g_i(Q_{i-1}, X_i, Y_i) = Q_i. The key is that the mutual information I(X_i; Z_i) and I(X_i; Q_i) must be 0 at every step and that at the end, Q_n = n*E[X_1 + ... + X_n]. Enforcing both of these together is not easy and might not be possible; I have to think about it for a while longer.
Fortunately, if any solution works, it'll probably be one where all the X's are i.i.d., all the Y's are i.i.d., all the f's are the same, and all the g's are the same. I originally proposed that f and g be addition and subtraction; unfortunately I'm not sure that those are going to work. I had something promising going where X_i and Y_i were both uniform distributions on the set {0, 1} and f and g were the binary XOR operations, but that doesn't give the average in the end.
I'm assuming here that "can't derive any information" really means "the mutual information between the r.v. that any professor receives and the r.v. of any other professor's salary is always zero", which seems like the only good interpretation that doesn't make the question trivially impossible. That formalizes the problem and makes it possible to construct a rigorous proof.