Two people, Abraham and Benjamin, are each given a subset of the integers from
1 to n. They
want to determine whether the two subsets have any integers in common.
Unfortunately, the channel through which they are able to communicate limits
the amount of information that can be passed through it. Abraham and Benjamin
are
therefore looking for a communication protocol that requires transferring only
a finite and bounded number of bits between them, regardless of n.
(So, O(1) bits of communication in total.)
After trying for a while, unsuccessfully, to come up with such a protocol,
Abraham and Benjamin realize that there is a loop-hole that they can,
potentially, employ: There is a computer, which we'll nickname "Computer O",
that both Abraham and Benjamin have access to
through communication channels that are unlimited in
capacity. (They can communicate with Computer O
Unfortunately, Computer O is programmed to do only one thing: it accepts an
order permutation,
Abraham and Benjamin cannot re-program Computer O to perform any other task.
They cannot see each other's inputs to the program.
They cannot even reprogram Computer O to work on permutations of any
size other than The question: Can Abraham and Benjamin figure out whether the two subsets they received have any commonalities, taking into account that they can enlist the help of Computer O? If not - show why; if so - show how. |
## List of solvers:Adam Daire (5 October 05:21)Daniel Bitin (7 October 20:21) Jan Fricke (30 October 22:09) |

Elegant and original solutions can be submitted to the puzzlemaster at __riddlesbrand.scso.com__.
Names of solvers will be posted on this page. Notify if you don't want
your name to be mentioned.

The solution will be published at the end of the month.

Enjoy!