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:

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={l₁,...,l_n} and R={r₁,...,r_n}. There is an edge in G from l_i to r_j if and only if Abraham's permutation maps i to j. Similarly, there is an edge from r_i to l_j 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 l_i to r_j with i>j and, for the same reason, it has at most one edge from r_i to l_j 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 l_i and r_i 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 l_i and r_i 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, l_j must belong to the same connectivity component as r_i and r_j must belong to the same connectivity component as l_i. 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 n₁₁ is the number of common elements, n₁₀ is the number of elements only in Abraham's set, n₀₁ - the number of elements only in Benjamin's set and n₀₀ - the number of elements missing altogether.

We want to calculate the parity of n₀₀. Both sides know the parity of n₀₀+n₀₁+n₁₀+n₁₁ (this is simply n), and both sides can safely assume that n₁₁=0, for the purposes of this calculation. We can now use the fact that Abraham knows the parity of n₁₀+n₁₁=n₁₀ (the elements in his subset) and Benjamin knows the parity of n₀₁+n₁₁=n₀₁ (the elements in his subset). Subtracting the two known parities from n yields the desired parity, given the assumption n₁₁=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 n₁₁=0 then n₀₀ 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.

Back to riddle

Back to main page