Using your Head is Permitted

October 2010 riddle

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 in addition to being able to send and receive O(1) bits in each direction through the direct communication line between them.)

Unfortunately, Computer O is programmed to do only one thing: it accepts an order permutation, A, in [1..n] from Abraham and an order permutation, B, in [1..n] from Benjamin, after which it computes whether the combined permutation AοB has exactly one cycle. This result, a Boolean, is then transferred back to both Abraham and Benjamin, and following this Computer O's software terminates permanently.

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 n. Furthermore, they cannot run Computer O's program more than once: once a pair of permutations is analyzed and a Boolean is returned, the computer halts and cannot be queried again.

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


To solution

Back to main page