Steven Strogatz is back, with his second math article in the weekly NY Times series which will go for 15 weeks. This one is called Rock Groups. He mentioned a puzzle series by John Tierney, and the one posted today reminds me of a problem I've posed in my Math for Elementary Teachers course - but this one's got a better storyline.
The Problem
Sol, at Wild About Math, asked for help solving a problem his brother heard on the radio:
Bob and Alice are both millionaires. They’re both curious to know who is richer but they don’t want to tell the other one how much money they have. Without engaging a trusted third party, how can they both know who is richer?
I have played with a similar problem that I think goes like this:
10 mathematicians are out to dinner, and want to know their average salary. Without anyone finding out anyone else’s salary, how can they do this?
I remember that I saw the solution and liked it. (I may have solved it myself, even, but I'm stumped again now - the delights of a bad memory...)
Sol wants the answer. I'd prefer hints, myself.
Posts
Does this have to be all numerical/algebraic?
ReplyDeleteThey could rig up some kind of balance scale where they could each only one side of it. Then they could put a weight, scaled to their net worth, on their own side, and they would be able to see which side was heavier without being able to see the amount on the other side.
But I suppose they would be able to see if the other side was a little more/less or WAY more/less, which I think in an ideal solution you wouldn't want to know that either.
Nice! This is a lot like one of the solutions given at Wild About Math.
ReplyDeleteI think there must be a solution like
ReplyDeleteAlice picks a number a and sends it to Bob.
Bob picks a number b and sends back a+b.
Alice adds her salary A and sends back a+b+A
Bob adds his salary B and sends back a+b+A+B.
But this won't work, since after the first part both Alice and Bob know the values of a and b.
There must be a way to toss in some extra values such that this doesn't happen. Maybe Alice sends a+x and then Bob adds in b+y and then Alice adds A-x to that total and so on ... so Bob knows a+x and A-x but not a or A? Something like that?
This falls under a class of problems in computer science known as "Zero knowledge proofs" see this for an explanation: http://en.wikipedia.org/wiki/Zero-knowledge_proof
ReplyDeleteJoshua's answer is close. Each in turn picks a random number, adds his or her salary and adds to the number passed to them (except in the first case). The sum makes a second "loop" then where each person subtracts the random number previously added. The last person in the second go-around has the sum of the salaries.
ReplyDelete