Jason (jcreed) wrote,
Jason
jcreed

http://gurmeet.net/puzzles/

An awesome list of math/programming/thinky puzzles:
http://gurmeet.net/puzzles/

I rather liked this one: ("Perplexing Polynomials")
"Alice is allowed to choose an arbitrary polynomial p(x) of any degree with nonnegative integer coefficients. Bob can infer the coefficients of p(x) by only two evaluations as follows. He chooses a real number a and Alice communicates p(a) to him. He then chooses a real number b and Alice communicates p(b) to him."

Also: ("Average Salary")
"Four honest and hard-working computer engineers are sipping coffee at Starbucks. They wish to compute their average salary. However, nobody is willing to reveal an iota of information about his/her own salary to anybody else. How do they do it?"


I feel like the condition "nobody is willing to reveal an iota of information about their own salary to anybody else" isn't exactly satisfied by the given solution. Or at least not as much as you'd like it to.

Call the four programmers Alice, Bob, Carol, and Dave. Alice chooses a random number rA uniformly between 0 and K-1 where K is assumed to be way bigger than any plausible sum of their 4 salaries. Alice says rA + sA to Bob, where sA is Alice's salary, and addition is assumed to be mod K. Bob says rA + sA + sB to Carol, Carol says rA + sA + sB + sC to Dave, Dave says rA + sA + sB + sC + sD to Alice, and Alice subtracts (mod K) rA to get the desired sum. The distribution of each message to every participant is uniformly random over [0,K-1], as desired, but there exist two sets of two participants who can collude to find the salary of the remaining two: together, Alice and Carol can compute (rA + sA + sB) - (rA + sA) = sB or (rA + sA + sB + sC + sD) - (rA + sA + sB + sC) = sD. Similarly, Bob and Dave can together compute (rA + sA) - (rA + sA + sB + sC + sD) + (sA + sB + sC + sD) = sA and (rA + sA + sB + sC) - (rA + sA + sB) = sC.

So you'd like to be necessary that all the other participants in the protocol to find a given person's salary. (Certainly it is sufficent if all other parties collude: the global sum is known, and they can just sum up all their salaries and subtract them from the global sum to find the non-colluder's) I think (but I'm not totally sure) the following protocol works for 4 people:

(Write rXYZ... to mean rX + rY + rZ + ... and sXYZ... to mean sX + sY + sZ + ....)
Alice generates rA, says rA + sA to Bob
Bob generates rB, says rAB + sAB to Carol
Carol generates rC, says rABC + sABC to Dave
Dave generates rD, says rABCD + sABCD to Alice
Alice subtracts rA in order to say rBCD + sABCD to Carol
Carol subtracts rC in order to say rBD + sABCD to Bob
Bob subtracts rB in order to say rD + sABCD to Dave
Dave subtracts rD in order to say sABCD to everyone.

The idea is that there's two rounds, and the ordering of the second round (ACBD) is sufficiently different from the first round (ABCD) that for any two participants that "surround" a third during the first round (in the sense that Alice and Carol together see the information going in and out of Bob, and so can deduce exactly how he's altering the randomized sum) are adjacent during the second round of the protocol, and vice-versa.

I went through and tediously checked all six pairs of participants and I think I convinced myself through sketchy linear-algebra reasoning that they can't find the specific salary of either of the remaining two participants, but I might have screwed up.

I wonder if there's a generalization to more people...

---

Ah, here's a generalization that works, but is more expensive than I expected. It uses Θ(n2) point-to-point messages and Θ(n) broadcast messages and requires Θ(n2) random numbers to be generated. In particular, for 4 participants, the below protocol requires 12 point-to-point messages, and 4 broadcast messages, and 8 random numbers, whereas the above requires only 7 point-to-point, 1 broadcast, and 4 random numbers.

Let there be n participants. Every participant x (whose salary is sx) generates n-2 random numbers r1, ... r(n-2), and sends n-1 messages, one to each participant y1, ... y(n-1) ≠ x. x sends r1 to y1, r2 to y2, ... r(n-2) to y(n-2), and (sx - (r1 + r2 + ... r(n-1))) to y(n-1). Each participant computes the sum of all the messages they receive during this first round, and broadcasts it. The sum of the messages each participant receives during the second round (which are all broadcast, so all participants receive the same set) is the desired sum of salaries.
Tags: math, puzzles
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 18 comments