Skip to content

Instantly share code, notes, and snippets.

@zou3519
Last active December 10, 2017 02:25
Show Gist options
  • Save zou3519/bd109024440f22c127b03f8394a408f6 to your computer and use it in GitHub Desktop.
Save zou3519/bd109024440f22c127b03f8394a408f6 to your computer and use it in GitHub Desktop.
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