Using your Head is Permitted

October 2010 solution

They can.

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

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:

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:

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.

Back to riddle

Back to main page