wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Puzzle: Who gets larger salary?
        
(Message started by: balki on Sep 10^th, 2009, 7:40am)

Title: Puzzle: Who gets larger salary?
Post by balki on Sep 10^th, 2009, 7:40am

Two persons A and B wants to know who gets more salary but they wont disclose their salaries to each other. How both can know who gets more and who gets less?

Title: Re: Puzzle: Who gets larger salary?
Post by SMQ on Sep 10^th, 2009, 8:24am

One possibility involving a third party C:

Let's call A's salary a and B's salary b.
Step 1: A and B secretly (without C's knowledge) agree on two numbers p (not zero) and q.
Step 2: A secretly tells C the number x = pa + q
Step 3: B secretly tells C the number y = pb + q
Step 4: C announces which of x or y is greater, but not by how much.

A and B now know whose salary is greater: if p is positive then x > y implies a > b and vice versa, otherwise if p is negative then x > y implies b > a and vice versa. Neither A nor B knows any more than this, and C, not knowing p or q, also doesn't know anything about a or b -- not even which one is greater (since p could be negative). As long as everyone follows the rules exactly no additional information is leaked.

--SMQ

Title: Re: Puzzle: Who gets larger salary?
Post by Eigenray on Sep 10^th, 2009, 2:10pm

Since there is obviously a huge demand for such third parties, I wonder why www.whichislarger.com, etc., are still available?

Title: Re: Puzzle: Who gets larger salary?
Post by SMQ on Sep 10^th, 2009, 7:17pm

on 09/10/09 at 14:10:07, Eigenray wrote:

Since there is obviously a huge demand for such third parties, I wonder why www.whichislarger.com, etc., are still available?

It's no longer available (http://whichislarger.com/). ;D

--SMQ

Title: Re: Puzzle: Who gets larger salary?
Post by R on Sep 13^th, 2009, 11:41pm

This (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1234838096) might help.

Title: Re: Puzzle: Who gets larger salary?
Post by R on Sep 13^th, 2009, 11:56pm

Well in this problem and in the problem of comparing ages (here (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1234838096)) use of third party is always discouraged.
I was wondering why can't we write a computer program for comparing two numbers, and get this program verified by anyone who wants to check. Once the program is verified, each party can enter their number (ages or salaries) in this program and just see the output. Nobody get to know what the numbers were and if you want you can shutdown the computer right after running this program so that no smart act can be done with the RAM content.

I couldn't figure out any reason for the invalidity of this solution. Please tell me one.

Title: Re: Puzzle: Who gets larger salary?
Post by towr on Sep 14^th, 2009, 1:05am

on 09/13/09 at 23:56:42, R wrote:

I couldn't figure out any reason for the invalidity of this solution. Please tell me one.

It is perfectly valid. As logn as they can both trust the computer; i.e. there is no keylogger, it isn't part of a botnet, nobody is recording the signals emitted by the keyboard or its sound (you can fairly well determine what someone types from the sound of the keyboard, with the right equipment) etc.

However, the real issue is that this problem is intended as a cryptography problem.

Title: Re: Puzzle: Who gets larger salary?
Post by R on Sep 14^th, 2009, 5:27am

on 09/14/09 at 01:05:45, towr wrote:

However, the real issue is that this problem is intended as a cryptography problem.

Yeah I totally understand. That's why the guy (http://www.proproco.co.uk/million.html) was so tense about it.

Title: Re: Puzzle: Who gets larger salary?
Post by raven on Sep 14^th, 2009, 10:54am

I'm not a cryptographer or mathematician or engineer or anything cool like that...so this is likely a silly response for this thread (yeah, I'm way out of my depth here)...but I propose this:

Use some representative medium that cannot be accurately reverse engineered to determine the input values, but can be otherwise readily compared using non-technical methods. Of course this is the sugar cubes in the box approach.

My idea was regulated water in water balloons and see which one is larger or weighs more; or adding saturation values to two color swatches and comparing which one appears darker when side by side...the water balloons approach is better because you can readily burst the balloon after the comparison phase.

The problem with this general approach is that if the results are close -- the person will have a pretty good guesstimate of the other person's value -- knowing their own value, and not having anything in place to randomize the results.

Since all we want here is a (</>) or (+/-) result and nothing more, and the rules suggest not using a third party to mediate the result...I instead propose a sorting process to find the result.

1. Person A (we will call Bob) and person B (we will call Alice) agree upon a common scale to represent the possible outside range (edges) of their incomes -- say 1...10 with 1 being $1 million annually, and 10 being $10 million annually.

2. Now they take that scale and find the middle point. They both answer if their respective incomes fall above or bellow that middle point. If one is above and one is bellow, they have their answer; if both are above or both are bellow, they repeat the process using the half-range in which they both fall, as the new scale.

* This method works better the fewer steps needed before determining the result. That is: both parties gain increased awareness of the other parties income with each additional step.

Title: Re: Puzzle: Who gets larger salary?
Post by Eigenray on Sep 14^th, 2009, 5:13pm

I bet you could do it using [link=http://en.wikipedia.org/wiki/Titration]titration[/link]. Person A prepares the titrant and tells person B how much titrand they should use for each dollar of their salary (the concentration can be adjusted too so A can't tell how much B is really adding). If it changes color, B > A (to within experimental error).