Problem:
Show that every consistent 2-configuration of order 4 on a finite set has a subset that is a consistent 2-configuration of order 2.
Solution
Solution:
First, assume the 2-configuration has just one cell. We claim there exists a sequence of elements of (not necessarily all distinct) such that the list
contains each element of the 2-configuration exactly once. To see this, consider the longest sequence such that are all distinct elements of the 2-configuration. (We may take if necessary. Note that the finiteness condition ensures such a maximal sequence exists.) Each element of occurs an even number of times among these pairs (since each occurrence in the sequence contributes to two pairs). If every element occurs 4 times or 0 times, then the elements occurring in the sequence form a cell, since they cannot occur in any other pairs in the 2-configuration. Hence, they are all of , and our sequence uses all the pairs in the 2-configuration, so the claim follows. Otherwise, there is some element occurring exactly twice. Choose so that is one of the two pairs in the 2-configuration not used by our sequence. Then choose so that is another pair not used thus far. Continue in this manner, choosing new elements with a pair not already used, until we reach a point where finding another unused pair is impossible. Now, our pairs so far are
Every element is used in an even number of these pairs, except possibly , which is used in three pairs, and , which is used in an odd number of pairs (so one or three) unless , in which case this element occurs four times. But since it is impossible to continue the sequence, must indeed have been used four times, so .
But now we can construct the following sequence of distinct elements of the 2-configuration:
This contradicts the maximality of our original sequence. This contradiction means that our original sequence must have used all the pairs in the 2-configuration, after all.
So we can express the 2-configuration via such a sequence of pairs, where each pair's second element equals the first element of the next pair. If has elements, then (since each element appears in four pairs) we have pairs. So we can choose the 1st, 3rd, 5th, th pairs, and then each element of belongs to just two of these pairs, because each occurrence of the element as an contributes to two consecutive pairs from our original sequence (or the first and last such pairs). Thus, we have our consistent 2-configuration of order 2, as desired.
Finally, if consists of more than one cell, then the pairs within any given cell form a consistent 2-configuration of order 4 on that cell. So we simply apply the above procedure to obtain a consistent 2-configuration of order 2 on each cell, and then combining these gives a consistent 2-configuration of order 2 on , as desired.