## October 2010 solution

They can.

Consider what happens if both Abraham and Benjamin send to Computer O a permutation calculated as follows:

• First, place all x in the x'th place, for values of x within the set. (For Abraham: in Abraham's set; for Benjamin: in Benjamin's set.)
• Next, place each remaining x in the next available space after the x'th place (in cyclic order).
If there is some element in common, the combined permutation will send it to itself, so this permutation must contain more than one cycle (unless n=1).

It would have been nice if there had been exactly one cycle in the case of no commonalities, but this is not quite the case. Let us analyze the combined permutation on the assumption that the two sets have no element in common.

Let us consider the problem as a graph problem. Let G=<L,R,E> be a directed bipartite graph, with L={l1,...,ln} and R={r1,...,rn}. There is an edge in G from li to rj if and only if Abraham's permutation maps i to j. Similarly, there is an edge from ri to lj if and only if Benjamin's permutation maps i to j.

The combined permutation AοB describes how elements in R map to other elements in R through elements in L. If this combined permutation is cyclic, the graph G is connected, and vice versa.

Note that by construction G has at most one edge from li to rj with i>j and, for the same reason, it has at most one edge from ri to lj with i>j. Except for the two special elements that are the targets of these two edges, each element, on either side of the graph, must belong to a connectivity component that also contains a smaller-numbered element. The smallest-numbered element in each connectivity component must therefore be one of these two special elements. Consequently, there cannot be more than two connectivity components.

The question remains whether there is one component or two.

Suppose, for the moment, that in addition to there being no common elements, there is an odd number of elements that are missing from both sets. In particular, there is some i for which neither subset contains i.

It is clear that if both li and ri belong to the same connectivity component, this will be the only connectivity component of the graph. (To see this, simply renumber the elements i to 1, i+1 to 2, etc.. In the new numbering, the two elements li and ri are the two "special" elements.) Note also that if j is the next number (cyclically) after i such that j is missing from both sets, lj must belong to the same connectivity component as ri and rj must belong to the same connectivity component as li. This means that the coloring of elements associated with numbers missing from both sets alternates in a cycle of length 2. However, because we assumed that their total number is odd, a cycle of length 2 means a cycle of length 1, meaning that both elements must belong to the same connectivity component, meaning that there is a total of a single connectivity component and that the combined permutation AοB has a single cycle.

Let us recap:

• If there are common elements and n>1, Computer O will return "More than one cycle".
• If there are no common elements and the total number of elements missing from both sets is odd, Computer O will return "Only one cycle".
It would be difficult for Abraham and Benjamin to figure out whether the number of elements missing from both sets is odd. However, the trick is that they do not have to. It is enough for them to figure out whether the number is odd or even on the assumption that there are no common elements.

This turns out to be fairly easy to do. Suppose n11 is the number of common elements, n10 is the number of elements only in Abraham's set, n01 - the number of elements only in Benjamin's set and n00 - the number of elements missing altogether.

We want to calculate the parity of n00. Both sides know the parity of n00+n01+n10+n11 (this is simply n), and both sides can safely assume that n11=0, for the purposes of this calculation. We can now use the fact that Abraham knows the parity of n10+n11=n10 (the elements in his subset) and Benjamin knows the parity of n01+n11=n01 (the elements in his subset). Subtracting the two known parities from n yields the desired parity, given the assumption n11=0.

Abraham and Benjamin can therefore agree on the following protocol to tell them whether their two sets have common elements:

• Step 1: Abraham sends to Benjamin whether 1 is on his list. Benjamin sends to Abraham whether 1 is on his list.
• Step 2: If both have 1, stop. The two sets have commonalities.
• Step 3: Abraham and Benjamin exchange the parities of the number of elements in their respective sets.
• Step 4: If the sum of the parities exchanged is the same as the parity of n, Abraham and Benjamin "tweak" their sets (logically-speaking) as follows: If one of them has 1, that person erases it from his set. If neither has 1, Abraham adds it to his set. (This change doesn't change whether they have commonalities or not, but it does guarantee that if n11=0 then n00 is odd.)
• Step 5: Both Abraham and Benjamin calculate order permutations over [1...n] as described above (if an element exists in the set, the permutation sends it to itself; if it doesn't exist in the set, the permutation sends it to the next one that doesn't exist in the set, cyclically).
• Step 6: The permutations are sent to Computer O and the resulting bit is received by both parties.
• Step 7: Stop. If the bit received is "one cycle", there are no common elements. If the bit received is "more than one cycle" common elements do exist.

Interestingly, the fact that Abraham and Benjamin require Computer O's assistance in order to determine in O(1) direct communication whether their two sets have commonalities is a basic result in communication complexity.