Last active
December 10, 2017 02:25
-
-
Save zou3519/bd109024440f22c127b03f8394a408f6 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
n people: 0, 1, ..., n-1 | |
Each person i will receive, from Enlightened Santa Alter bot, a person j. | |
Encode this as an n-digit binary number, such that the jth element is 1 and everything else is 0. | |
For example, if the person i receives person 3, their 'secret' number is (zero-indexed) 000100...0 | |
Now, person i has some n-digit binary 'secret'. Call this x_i. | |
Construct n numbers (call them 'pieces'), {x_{i, 0}, x_{i, 1}, ..., x_{i, n-1}} | |
such that the XOR of all of them is equal to x_i. | |
Person i will send the piece x_{i, j} to person j. | |
Person i has received pieces x_{j, i} for all j. There are n such pieces (including x_{i, i}). | |
Person i will XOR all n received pieces x_{j, i} for all j. Let y_i be the result. | |
Now, all people 0, 1, ..., n-1 gather in a room and display their results y_0, y_1, ..., y_n. | |
XOR all of these numbers. The result should be 11111111 (n ones) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment