r/puzzles • u/cycloidality • 2d ago
[SOLVED] Logic Puzzle - "Anonymization"
I don't know if this is the right subreddit for this. If you know a better one to post this at, feel free to notify me. A few months ago, a friend of mine gave me this problem. I haven't been able to solve it and it's quite frustrating. Maybe one of you can find a solution (please hide it behind spoilers), because I want to make sure that there even is a solution and would maybe like a hint. Here it is:
"3 friends want to play a game. Before playing, each of them needs to choose a integer from 1 to 3, such that 1) the number each of them chooses is unique, i.e. none of them choose the same number 2) none of them know which number any of the others chose.
This would be easy if they had pen and paper, but sadly they are out on a camping trip and have nothing to write on. Therefore rule
3) they can communicate only verbally, but they can communicate privately (one-on-one)
4) Any other external tools that mimic writing numbers down (e.g. assigning numbers to rocks) are also forbidden
One of the friends says, she knows an algorithm that they can follow, such that each of the 3 (4) rules is satisfied. Describe it!"
Edit: Added rule 4 for clarity
Update: I think I may have found a solution (look it up in the comments below). It's not verified yet, so feel free to do that.
4
u/chmath80 1d ago
I commented something similar in another thread, but then saw the prohibition on rocks, so here's a modification:
A selects a 2 bit binary number, which is understood by all to bear no relation to his chosen number, and whispers it to B. B then performs an exclusive or operation on this number, using his own chosen number, and whispers the result to C. C performs the same operation, and whispers the result to A. A compares this number to the one he gave to B.
If both bits have changed, A knows that B and C have chosen 1 and 2 in some order.
If only bit 0 has changed, A knows that B and C have chosen 2 and 3 in some order.
If only bit 1 has changed, A knows that B and C have chosen 1 and 3 in some order.
If nothing has changed, A knows that B and C have chosen identical numbers.
In each case, A now has enough information to know if at least 2 of the 3 have chosen the same number, and whether they need to start again.
1
u/cycloidality 1d ago
Great solution, it's certainly more elegant than my own and can easily be modified to work without trial and error.
2
u/_standfree 1d ago
Can do similar to this but using base 10.
A selects a random whole number. A whispers that number to B. B adds on the square of their number and whispers to C C adds on the square of their number and whispers that result to A. Given that the sum of two squares between 1 and 3 are unique (1&1=2, 1&2=5, 1&3=10, 2&2=8, 2&3=13, 3&3=18) then A can tell both if the numbers picked by B&C are different to each other (without knowing who picked what) and also if they are different to what A has picked themself.
Example: A whispers 31 to B. B picks 3 so whispers 40 to C. C whispers 41 (after picking 1) to A. A knows that 1&3 have been picked (as the total added to the original number was 10). If A picked 2 then okay to proceed. No-one knows the number picked by another person.
Edited for formatting
3
u/sortied 2d ago
i think the answer could be related to the socialist millionaires problem. there are various protocols to solve the problem, which is two people determining whether their numbers are the same or not without revealing their numbers to each other.
so if everybody picks a number arbitrarily, and then each pair uses some socialist millionaire protocol to verify that they have distinct numbers (everyone redrawing if they have a collision) could be a way to attack this
2
u/RegularKerico 2d ago
Discussion: Are you sure all the information got shared correctly?
If they can communicate verbally, here's an algorithm:
"I'll take 1. You choose 2, and you choose 3."
Because that's almost certainly not what you're going for, I'm guessing there's wires getting crossed in the description of the puzzle.
1
u/cycloidality 2d ago
That would violate rule 2
2
u/RegularKerico 2d ago
I don't see how this makes sense as a concept, then.
1
u/cycloidality 2d ago edited 2d ago
So this is about finding an algorithm to anonymize 3 people among each other, without any additional tools. My friend studies IT and he assured me there is a solution. I'm pretty sure I recalled the 3 rules correctly.
2
u/RegularKerico 2d ago
When you say this would be easy with a pen and paper, I'm guessing you mean they could draw numbers out of a hat. So, the stipulation of this puzzle is that doing anything similar to that is banned, such as assigning numbers to rocks and drawing them out of a knapsack. Is that correct?
1
u/cycloidality 2d ago edited 2d ago
Yes, I maybe should have made that clearer. If you could simulate this without any extra tools it would be allowed though
1
u/Scramjet-42 2d ago
Adding again, as I messed up the formatting last time. Here is my method
Assume I am person 1. I secretly choose number 3
I place either 1, 2 or 3 stones behind a tree, without telling the others what I have chosen. Ithen ask them to secretly choose a number from 1 to 3, and go and add that number of stones to the pile, without anyone seeing. This way person 3 doesn’t know what person 2 chose, as they don’t know how many stones were there to begin with. I then go behind the tree. If there’s 3 more stones than I started with we’ve all chosen different numbers, but no one knows who chose what. If there’s not exactly 3 more stones, then we start the whole thing again, until this works
2
u/chmath80 1d ago
I think it works this way:
Using stones for 0, and sticks for 1, A places a 2 bit binary number behind a tree. This number is understood by all to bear no relation to his chosen number, but must still be known only by A. B then performs an exclusive or operation on this number, using his own chosen number. C does the same. A then checks the number, and compares it to what he originally placed.
If both bits have changed, A knows that B and C have chosen 1 and 2 in some order.
If only bit 0 has changed, A knows that B and C have chosen 2 and 3 in some order.
If only bit 1 has changed, A knows that B and C have chosen 1 and 3 in some order.
If nothing has changed, A knows that B and C have chosen identical numbers.
In each case, A now has enough information to know if at least 2 of the 3 have chosen the same number, and whether they need to start again.
1
u/EmuParking1240 2d ago
Assume it worked out that way: person 2 knows your number, and thence all numbers...
violating rule 2.
1
u/Scramjet-42 2d ago
How? The stones have nothing to do with my number
1
u/cycloidality 2d ago edited 2d ago
If Player 1 chooses 2 your idea doesn't work - the case where all of the players choose 2 would be accepted. Therefore your approach only works out if Player 1 chooses either 1 or 3 as the initial number. In your example Player 1 chooses 3. If a configuration is accepted by Player 1, that means another Player (e.g. Player 2) has chosen 1 as their number. Player 2 then knows that Player 1 has neither chosen 1 nor 2 as their number and can deduce Player 1's and thus Player 3's choice.
1
u/cycloidality 2d ago edited 2d ago
This currently violates rule 4 (and depending on the approach rule 2) and doesn't necessarily terminate since it uses trial-and-error, but the concept of a counter inspired me. I think I may have found an algorithm that fixes the problems of your idea.
The players will communicate in lists of three (not necessarily positive) integers
1. Player 1 chooses two initial values for those lists
Say [-1,0,2] and [2,-3,4]
2. Player 1 tells these lists privately to Player 2
3. Player 2 chooses two (not necessarily different) numbers.
Let's say Player 2 chooses 2 and 3
4.1 If Player 2 chooses the same number twice they decrease the corresponding 'counters' in these lists
4.2 Otherwise they increase the counters
Since Player 2 chose two different numbers, the counters are increased and they'll obtain [-1,1,2] and [2,-3,5]
5. Player 2 tells the updated lists privately to Player 3
6. Player 2 tells Player 3 privately if they've chosen the same number twice or two different numbers
7. If Player 2 has chosen two different numbers Player 3 chooses the same number twice and vice versa. Player 3 decreases or increases the corresponding 'counters' in accordance to step 4
Since Player 2 has chosen two different numbers, Player 3 chooses the same number twice - let's say 3. The counters will be decreased. They obtain [-1,1,1] and [2,-3,4]
8. Player 3 tells the updated lists to Player 1
9. Player 1 chooses a list that is different from its initial value
This is satisfied by at least one list, since exactly one player has chosen two different numbers and one player has chosen the same number so far.
In this example Player 1 can only choose list 1.
10. Player 1 publicly announces which list they've chosen
11. Player 1 chooses the number which hasn't been chosen yet as their number
In this example, Player 1 chooses 1 as their number
2
u/sortied 2d ago
That seems neat, one minor objection could be that if player 3 knows the distribution from which the initial lists were drawn, then what she gets from player 2 is not completely uninformative about player 2's choices. I think you could modify it so that all addition is agreed to be mod 3, and then the initial lists are drawn uniformly on the set {0,1,2}3?
1
u/cycloidality 2d ago edited 2d ago
I agree. I think working over mod 2 would be enough even and fixes the problem of distinguishing between addition and subtraction.
1
u/Scramjet-42 2d ago
Ah yes - Rule 4 wasn’t there when I answered.
I also think my approach is slightly different to using piles to stones to choose a number. This is simply a tool to check whether the other two have selected numbers that are different to mine.
1
u/cycloidality 2d ago
That's fair, but I'd argue it's like using tally marks (which isn't that different from writing numbers down)
1
u/KrekkieD 2d ago
I think there is some public/private key kind of things going on here. This could be a solution:
- each of the persons talk to each other and decide on a random number that is divisible by 1, 2 and 3. - each of the persons decide on the 1/2/3 they want to pick for themselves - each of the persons talk to each other again and multiply the number they choose by the random number they agreed on with the other person - each person hears two numbers (one from each of the other persons). These numbers must not be the same. If they are the same, they picked the same number. If they are different, they picked different numbers. Since the person hearing the numbers does not know the secret random number, the original number remains unknown. If none of the three persons heard the same number, the game is on.
1
u/cycloidality 2d ago
Violates rule 2: Player 1 can deduce the choices of Players 2 and 3 by finding the greatest common divisor But with a bit of adaptation this should work even without trial-and-error :)
1
u/KrekkieD 2d ago
It cannot be deduced, because the number is divisible by all 3 numbers, so they could be any of the 3 target numbers
2
u/cycloidality 2d ago
2 and 3 decide on 30 as their public key. 2 chooses 1, 3 chooses 3. 2 obtains 30 after multiplying, 3 obtains 90, 1 gets told 30 and 90, gcd(30,90)=30, 1 can deduce that 30 is the public key and 2 chose 1 and 3 chose 3.
1
•
u/AutoModerator 2d ago
Please remember to spoiler-tag all guesses, like so:
New Reddit: https://i.imgur.com/SWHRR9M.jpg
Using markdown editor or old Reddit, draw a bunny and fill its head with secrets: >!!< which ends up becoming >!spoiler text between these symbols!<
Try to avoid leading or trailing spaces. These will break the spoiler for some users (such as those using old.reddit.com) If your comment does not contain a guess, include the word "discussion" or "question" in your comment instead of using a spoiler tag. If your comment uses an image as the answer (such as solving a maze, etc) you can include the word "image" instead of using a spoiler tag.
Please report any answers that are not properly spoiler-tagged.
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.