wu :: forums - Print Page


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

        riddles >> medium >> GHETTO ENCRYPTION II
        
(Message started by: twitceh on Nov 28^th, 2006, 11:30am)

Title: GHETTO ENCRYPTION II
Post by twitceh on Nov 28^th, 2006, 11:30am

I haven't been able to find the solution to this riddle, could anyone tell me the answer to it? Thanks.

Title: Re: GHETTO ENCRYPTION II
Post by towr on Nov 28^th, 2006, 2:00pm

For reference, here's the actual riddle referred to:

Quote:

Three coworkers would like to know their average salary. However, they are self-conscious and don't want to tell each other their own salaries, for fear of either being ridiculed or getting their houses robbed. How can they find their average salary, without disclosing their own salaries?

There are a number of options.
For example [hide]Each adds a random number to their salary. Then they add all the numbers, then each subtracts his random number. And then divide the result by three to get the avarage[/hide]

Title: Re: GHETTO ENCRYPTION II
Post by twitceh on Nov 30^th, 2006, 3:25pm

Oh, I see :) Thanks! Are there any other methods to find this out?

Title: Re: GHETTO ENCRYPTION II
Post by Icarus on Nov 30^th, 2006, 7:32pm

Towr's method must be done with great care. Whenever one person passes his result to the next, they must be sure that the third does not know what number is passed. Otherwise the third person at the end will have enough information to deduce the other two.

Call the employees A, B, C; with salaries a, b, c, and codes x, y, z. The process is:

A passes (a+x) to B
B passes (a+x+b+y) to C
C passes (a+x+b+y+c+z) to A
A passes (a+b+y+c+z) to B
B passes (a+b+c+z) to C
C reveals (a+b+c) to all.

At the end,
A knows: a, x, b+c+y+z, a+b+c; from which he can derive b+c and y+z, but not the individual values.
B knows: b, y, a+x, a+b+c+z, a+b+c from which he can derive z, a+c, c-x, but not the individual values of a and c.
C knows: c, z, a+x+b+y, a+b from which he can derive x+y, but no individual values.

Any other method of passing reveals too much to at least one person.

-------------------------
An alternative is simply to use a calculator with its display covered. Each carefully adds their own salary, then they divide by 3 and look at the result.

Title: Re: GHETTO ENCRYPTION II
Post by denis on Dec 6^th, 2006, 4:17pm

How about this method?

I came up with this and as this is my first post, would like to know if I missed something.

Say employee A, B, C have salary a,b,c
A,B,C each choose a multiplyer at random x,y,z respectively.

A passes ax to B
B passes axy to C
B passes by to A
A passes bxy to C
C passes cz to A
A passes cxz to B
C now has (axy, bxy) and passes (axy+bxy)z to B
B multiplies cxz by y and returns (a+b+c) xyz to A
A divides by x and passes (a+b+c)yz to B
B divides by y and passes (a+b+c)z to C
C divides by z and reveals (a+b+c)/3

Ok it uses up more steps than the previous solution but can anyone deduce individual salaries from this? Should z,y,z be prime numbers or does it make any difference?

Thanks for your feedback.
« Last Edit: Today at 3:56pm by denis »

Title: Re: GHETTO ENCRYPTION II
Post by bement14 on Dec 6^th, 2006, 6:05pm

A simple way would be for the employees all to create 5 numbers that when averaged equaled their salaries, and then the employees culd add the numbers on similar peices of paper into a pile and then when they averaged all of the papers they would get the average for the group. This wouldn't be the perfect way to do it, but how secret can you expect to keep your number in a group of three if one number varies greatly from the other two.

Title: Re: GHETTO ENCRYPTION II
Post by towr on Dec 7^th, 2006, 1:09am

on 12/06/06 at 16:17:42, denis wrote:

Ok it uses up more steps than the previous solution but can anyone deduce individual salaries from this? Should z,y,z be prime numbers or does it make any difference?

B knows ax, (a+b+c)xyz and (a+b+c)yz from the last two he can deduce x, and then with the first a.

Changing the order should work though, since multiplying is equivalent to adding logarithms, and addition works fine.

Title: Re: GHETTO ENCRYPTION II
Post by denis on Dec 7^th, 2006, 9:17am

Towr,

Thanks for your input. Indeed the order should be changed to fix the problem.

So if A passes (a+b+c)yz to C instead of B and then C passes (a+b+c)y to B it should be OK.

Title: Re: GHETTO ENCRYPTION II
Post by ispollock on Apr 16^th, 2007, 6:44pm

Hullo; first post, although I've been doing these riddles for a while.
I'm sure the pure math methods work, but if we're talking about an hourly wage in dollars or pounds or what have you, wouldn't the easiest solution be for the three people to put a number of objects equal to their wage, say 25 paperclips for $25/hr, into a pot, then count them all out and divide by three? Maybe it isn't as elegant but it seems to me it would work quite well, at least for an hourly wage which is usually more or less an integer value.
Cheers,
-Ian

Title: Re: GHETTO ENCRYPTION II
Post by denis on Apr 16^th, 2007, 7:26pm

Huh... My first post on this forum was made in this thread on Dec 6 2006..

Feels like much longer ago....

Hi Ispollock. Yes, your method looks like it works OK if you don't mind loosing the part that comes after the decimal in the hourly wage.

Title: Re: GHETTO ENCRYPTION II
Post by towr on Apr 17^th, 2007, 12:17am

on 04/16/07 at 19:26:39, denis wrote:

Hi Ispollock. Yes, your method looks like it works OK if you don't mind loosing the part that comes after the decimal in the hourly wage.

You could use paperclips for the dollars and thumbtacks for the cents, or something like that..

Title: Re: GHETTO ENCRYPTION II
Post by penguin_man on Apr 20^th, 2007, 2:56am

my fist thought was ...

person A- puts salary into calculator and pluses 0
(this is so the next person cant see his salary)

person B and c- do the same

divide answer by three.

this doesnt work if person B presses = when he recieves the calculator

Title: Re: GHETTO ENCRYPTION II
Post by rmsgrey on Apr 20^th, 2007, 8:30am

on 04/20/07 at 02:56:28, penguin_man wrote:

Many calculators display the current running total when an operator is entered.

Better would be to use the M+ key to add the entered values to the calculator's memory - though that relies on B being honest enough not to check A's entered data...

Title: Re: GHETTO ENCRYPTION II
Post by Product on Apr 26^th, 2007, 12:49pm

My idea:

Each man writes down his salary and two fake salaries, each on a seperate slip of paper. The slips are placed in a hat without the other two seeing what is written on them. Randomly, the strips are drawn and written on one sheet of paper, each man remembering his two fake salaries. The nine salaries are added together and the number is written on another sheet of paper. The original paper is destroyed. The first man subtracts the sum of his two fake salaries from the number, and writes that number down. The other two men do this as well. The end result should be the sum of their actual salaries, which they can divide by three for the answer.

Thoughts?

Title: Re: GHETTO ENCRYPTION II
Post by Icarus on Apr 26^th, 2007, 4:28pm

That is essentially the technique towr described (which he probably obtained from an earlier thread for this same puzzle).

The differences from towr's make the salaries slightly less secure, as it lets the others know that your salary is one of only six possibilities.

Title: Re: GHETTO ENCRYPTION II
Post by thinktank on Apr 28^th, 2007, 8:05am

the riddle says that the people cant tell each other their salaries, but why cant they say call another neutral guy, and just tell him to find out the average, without telling him what the numbers signify.

Title: Re: GHETTO ENCRYPTION II
Post by Icarus on Apr 28^th, 2007, 4:22pm

Most companies strongly frown on you divulging your salary to anyone without a direct need to know. In fact many will even fire you for divulging it to someone else where you work.

Title: Re: GHETTO ENCRYPTION II
Post by thinktank on Apr 29^th, 2007, 12:02am

then what about using a software, where the respective people enter their salaries, the software calculates the average, and then deletes itself from the hardware memory

Title: Re: GHETTO ENCRYPTION II
Post by javacodeman on Jul 6^th, 2007, 8:33am

Here's my low tech solution which is similar to the paperclip/tack solution:

Place a ballot box with three locks into a room. Each of the three employees place a lock on the box and then individually place a representation of 1/3 of their annual wage into the box (fake money would work well). Once all three have completed the task, they can open the box and count the money. They would have their average.

java

Title: Re: GHETTO ENCRYPTION II
Post by asavla on Mar 6^th, 2008, 12:08pm

It's been a while since I thought about this, but here would be my answer for persons A, B, & C, with their corresponding salaries: a, b, & c.

1.) A tells B his salary plus a random number (a + x).
2.) B tells C the previous number plus his own (a + b + x).
3.) C tells A the new number plus his salary (a + b + c + x)

4.) A now subtracts out x and divides by 3: ((a + b + c)/3).
Voila.

Title: Re: GHETTO ENCRYPTION II
Post by murdok03 on Oct 3^rd, 2012, 5:05am

Well I found an ugly solution to this but it's worth reading.

Each choose to mask some of the digits from the salary figure. And pass the new figure to the left while passing the figure with the reverse mask to the right.
I'm thinking odd vs even digits but any mask will work.
Example for 121212 you pass to the left 101010 and 020202 to the right.
Each so receives 2 numbers that he adds to his own salary.
X = A + digits from B + digits from C
Y = digits from A + B + digits from C
Z = digits from A + digits from B + C
They all publish XYZ and add them up.
It's X+Y+Z = 2 *( A + B + C )

It's better if the number has many different digits, something like 1K will look suspicious.
Any 2 can figure out the 3'rd salary.

Title: Re: GHETTO ENCRYPTION II
Post by rmsgrey on Oct 4^th, 2012, 4:51am

You won't know the precise value, but you will know a lower bound for each of the others' salaries.

If you have a 5 figure salary, B hands you a 7-figure number, and C hands you a 4-figure value, then you're probably happy to rob B's place even without knowing his exact income...

Title: Re: GHETTO ENCRYPTION II
Post by sergeylukin on Mar 30^th, 2013, 2:32pm

on 03/06/08 at 12:08:22, asavla wrote:

1.) A tells B his salary plus a random number (a + x).
2.) B tells C the previous number plus his own (a + b + x).
3.) C tells A the new number plus his salary (a + b + c + x)

4.) A now subtracts out x and divides by 3: ((a + b + c)/3)

I vote for this solution. It makes sense to me.

Title: Re: GHETTO ENCRYPTION II
Post by RudolfPotucek on Jan 6^th, 2018, 11:04pm

I would suggest this:

Each person splits their salary into two numbers that add up to the actual salary. The parts can be negative. Then they hand each paert to a different person:

A: S_A1 -> B, S_A2 -> C
B: S_B1 -> A, S_B2 -> C
C: S_C1 -> A, S_C2 -> B

That way each person ends up with 2 numbers to sum:

A: S_B1 + S_C1 -> N_1
B: S_A1 + S_C2 -> N_2
C: S_A2 + S_B2 -> N_3

They can now safely pool these numbers to calculate the average:

A = (N_1 + N_2 + N_3) / 6

Title: Re: GHETTO ENCRYPTION II
Post by rmsgrey on Jan 7^th, 2018, 5:02am

on 01/06/18 at 23:04:27, RudolfPotucek wrote:

A = (N_1 + N_2 + N_3) / 6

Since N_1 + N_2 + N_3 is the combined total salary, you only want to divide by 3, not by 6.

on 10/03/12 at 05:05:19, murdok03 wrote:

Any 2 can figure out the 3'rd salary.

That's true whatever method you use - the whole point is that, in the end, everyone knows (a+b+c)/3, and everyone knows their own salary, so any two people between them have enough information to deduce the third person's salary without needing to know any information from intermediate steps.