Given set of $2m$ elements, randomly group them into $m$ pairs. Create another $m$ pairs by once again randomly pairing elements from the set.

Example. Given m=3, $\{1,2,3,4,5,6\}$
Randomly pairing twice: $(1,3)$ $(2,4)$ $(5,6)$ and $(1,5)$ $(2,3)$ $(4,6)$
The original set can be reconstituted by selecting $1,2,6$ and $5,3,4$

There are $2^{2m}$ possible selections. Will at least one of these always reproduce the original set? Or alternately, does there exist a pairing regimen that makes reconstituting the original set impossible?


Yes, there will always be at least two such selections.

For simplicity remove any pairs that are identical in both pairings (each of which has itself 2 ways of selection to rebuild the original set). Then the remaining pairs can define the edges of a graph where every vertex is degree $2$ and the graph is bipartite, since all cycles are even due to the alteration of edges from each pairing. Then each such cycle can be selected from in two ways from the two pairings.

Example graphed out, red lines representing the first pairing selection $(1,3),(5,6),(7,2),(4,8)$ and blue lines the second pairing $(1,2),(5,3),(7,8),(4,6)$:

enter image description here

The rebuild of the original set can be achieved by choosing either $1,5,7,4,2,3,8,6$ or $3,6,2,8,1,5,7,4$

| cite | improve this answer | |
  • $\begingroup$ Thank you! This is precisely the articulation I needed. $\endgroup$ – tgibson Sep 4 '17 at 19:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.