wu :: forums « wu :: forums - GHETTO ENCRYPTION II » Welcome, Guest. Please Login or Register. Feb 23rd, 2024, 4:55am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    medium (Moderators: SMQ, Eigenray, ThudnBlunder, Grimbal, william wu, towr, Icarus)    GHETTO ENCRYPTION II « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: GHETTO ENCRYPTION II  (Read 11354 times)
twitceh
Newbie

Posts: 4
 GHETTO ENCRYPTION II   « on: Nov 28th, 2006, 11:30am » Quote Modify

I haven't been able to find the solution to this riddle, could anyone tell me the answer to it? Thanks.
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: GHETTO ENCRYPTION II   « Reply #1 on: Nov 28th, 2006, 2:00pm » Quote Modify

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 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
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
twitceh
Newbie

Posts: 4
 Re: GHETTO ENCRYPTION II   « Reply #2 on: Nov 30th, 2006, 3:25pm » Quote Modify

Oh, I see Thanks! Are there any other methods to find this out?
 IP Logged
Icarus
wu::riddles Moderator
Uberpuzzler

Boldly going where even angels fear to tread.

Gender:
Posts: 4863
 Re: GHETTO ENCRYPTION II   « Reply #3 on: Nov 30th, 2006, 7:32pm » Quote Modify

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.
 « Last Edit: Nov 30th, 2006, 7:34pm by Icarus » IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
denis
Uberpuzzler

Gender:
Posts: 1222
 Re: GHETTO ENCRYPTION II   « Reply #4 on: Dec 6th, 2006, 4:17pm » Quote Modify

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?

« Last Edit: Today at 3:56pm by denis »
 « Last Edit: Dec 6th, 2006, 4:50pm by denis » IP Logged
bement14
Newbie

Posts: 1
 Re: GHETTO ENCRYPTION II   « Reply #5 on: Dec 6th, 2006, 6:05pm » Quote Modify

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.
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: GHETTO ENCRYPTION II   « Reply #6 on: Dec 7th, 2006, 1:09am » Quote Modify

on Dec 6th, 2006, 4:17pm, 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.

 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
denis
Uberpuzzler

Gender:
Posts: 1222
 Re: GHETTO ENCRYPTION II   « Reply #7 on: Dec 7th, 2006, 9:17am » Quote Modify

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.

 « Last Edit: Dec 7th, 2006, 9:19am by denis » IP Logged
ispollock
Newbie

Posts: 1
 Re: GHETTO ENCRYPTION II   « Reply #8 on: Apr 16th, 2007, 6:44pm » Quote Modify

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
 IP Logged
denis
Uberpuzzler

Gender:
Posts: 1222
 Re: GHETTO ENCRYPTION II   « Reply #9 on: Apr 16th, 2007, 7:26pm » Quote Modify

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.

 « Last Edit: Apr 17th, 2007, 5:19am by denis » IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: GHETTO ENCRYPTION II   « Reply #10 on: Apr 17th, 2007, 12:17am » Quote Modify

on Apr 16th, 2007, 7:26pm, 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..
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
penguin_man
Newbie

Posts: 1
 Re: GHETTO ENCRYPTION II   « Reply #11 on: Apr 20th, 2007, 2:56am » Quote Modify

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

this doesnt work if person B presses = when he recieves the calculator
 IP Logged
rmsgrey
Uberpuzzler

Gender:
Posts: 2872
 Re: GHETTO ENCRYPTION II   « Reply #12 on: Apr 20th, 2007, 8:30am » Quote Modify

on Apr 20th, 2007, 2:56am, penguin_man wrote:
 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

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...
 IP Logged
Product
Newbie

x * y

Posts: 10
 Re: GHETTO ENCRYPTION II   « Reply #13 on: Apr 26th, 2007, 12:49pm » Quote Modify

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?
 « Last Edit: Apr 26th, 2007, 12:50pm by Product » IP Logged
Icarus
wu::riddles Moderator
Uberpuzzler

Boldly going where even angels fear to tread.

Gender:
Posts: 4863
 Re: GHETTO ENCRYPTION II   « Reply #14 on: Apr 26th, 2007, 4:28pm » Quote Modify

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.
 IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
thinktank
Newbie

Posts: 10
 Re: GHETTO ENCRYPTION II   « Reply #15 on: Apr 28th, 2007, 8:05am » Quote Modify

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.

 IP Logged
Icarus
wu::riddles Moderator
Uberpuzzler

Boldly going where even angels fear to tread.

Gender:
Posts: 4863
 Re: GHETTO ENCRYPTION II   « Reply #16 on: Apr 28th, 2007, 4:22pm » Quote Modify

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.
 IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
thinktank
Newbie

Posts: 10
 Re: GHETTO ENCRYPTION II   « Reply #17 on: Apr 29th, 2007, 12:02am » Quote Modify

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
 IP Logged
javacodeman
Newbie

Gender:
Posts: 7
 Re: GHETTO ENCRYPTION II   « Reply #18 on: Jul 6th, 2007, 8:33am » Quote Modify

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
 IP Logged
asavla
Newbie

Posts: 1
 Re: GHETTO ENCRYPTION II   « Reply #19 on: Mar 6th, 2008, 12:08pm » Quote Modify

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.
 IP Logged
murdok03
Newbie

Posts: 2
 Re: GHETTO ENCRYPTION II   « Reply #20 on: Oct 3rd, 2012, 5:05am » Quote Modify

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.
 IP Logged
rmsgrey
Uberpuzzler

Gender:
Posts: 2872
 Re: GHETTO ENCRYPTION II   « Reply #21 on: Oct 4th, 2012, 4:51am » Quote Modify

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...
 IP Logged
sergeylukin
Newbie

Posts: 1
 Re: GHETTO ENCRYPTION II   « Reply #22 on: Mar 30th, 2013, 2:32pm » Quote Modify

on Mar 6th, 2008, 12:08pm, 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.
 « Last Edit: Mar 30th, 2013, 2:35pm by sergeylukin » IP Logged
RudolfPotucek
Newbie

Posts: 1
 Re: GHETTO ENCRYPTION II   « Reply #23 on: Jan 6th, 2018, 11:04pm » Quote Modify

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

 IP Logged
rmsgrey
Uberpuzzler

Gender:
Posts: 2872
 Re: GHETTO ENCRYPTION II   « Reply #24 on: Jan 7th, 2018, 5:02am » Quote Modify

on Jan 6th, 2018, 11:04pm, 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 Oct 3rd, 2012, 5:05am, 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.
 IP Logged
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy => medium   - hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »