Maths Olympiad Prep

Library / /306 of 377

Combinatorics Difficulty 5.5 AIME, harder Prove it United States

Problem:
Show that every consistent 2-configuration of order 4 on a finite set AA 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 a0,a1,,ana_{0}, a_{1}, \ldots, a_{n} of elements of AA (not necessarily all distinct) such that the list
{a0,a1},{a1,a2},,{an1,an},{an,a0} \{a_{0}, a_{1}\}, \{a_{1}, a_{2}\}, \ldots, \{a_{n-1}, a_{n}\}, \{a_{n}, a_{0}\}
contains each element of the 2-configuration exactly once. To see this, consider the longest sequence such that {a0,a1},,{an1,an},{an,a0}\{a_{0}, a_{1}\}, \ldots, \{a_{n-1}, a_{n}\}, \{a_{n}, a_{0}\} are all distinct elements of the 2-configuration. (We may take n=0n=0 if necessary. Note that the finiteness condition ensures such a maximal sequence exists.) Each element of AA 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 AA, and our sequence uses all the pairs in the 2-configuration, so the claim follows. Otherwise, there is some element aia_{i} occurring exactly twice. Choose b1b_{1} so that {ai,b1}\{a_{i}, b_{1}\} is one of the two pairs in the 2-configuration not used by our sequence. Then choose b2b_{2} so that {b1,b2}\{b_{1}, b_{2}\} is another pair not used thus far. Continue in this manner, choosing new elements bkb_{k} with {bk,bk+1}\{b_{k}, b_{k+1}\} a pair not already used, until we reach a point where finding another unused pair is impossible. Now, our pairs so far are
{a0,a1},,{an1,an},{an,a0},{ai,b1},{b1,b2},,{bk1,bk}. \begin{gathered} \{a_{0}, a_{1}\}, \ldots, \{a_{n-1}, a_{n}\}, \{a_{n}, a_{0}\}, \\ \{a_{i}, b_{1}\}, \{b_{1}, b_{2}\}, \ldots, \{b_{k-1}, b_{k}\} . \end{gathered}
Every element is used in an even number of these pairs, except possibly aia_{i}, which is used in three pairs, and bkb_{k}, which is used in an odd number of pairs (so one or three) unless ai=bka_{i}=b_{k}, in which case this element occurs four times. But since it is impossible to continue the sequence, bkb_{k} must indeed have been used four times, so bk=aib_{k}=a_{i}.
But now we can construct the following sequence of distinct elements of the 2-configuration:
{a0,a1},,{ai1,ai},{ai,b1},{b1,b2},,{bk1,ai},{ai,ai+1},,{an1,an},{an,a0}. \begin{gathered} \{a_{0}, a_{1}\}, \ldots, \{a_{i-1}, a_{i}\}, \{a_{i}, b_{1}\}, \{b_{1}, b_{2}\}, \ldots, \{b_{k-1}, a_{i}\}, \\ \{a_{i}, a_{i+1}\}, \ldots, \{a_{n-1}, a_{n}\}, \{a_{n}, a_{0}\} . \end{gathered}
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 AA has nn elements, then (since each element appears in four pairs) we have 2n2n pairs. So we can choose the 1st, 3rd, 5th, ,(2n1)\ldots, (2n-1)th pairs, and then each element of AA belongs to just two of these pairs, because each occurrence of the element as an aia_{i} 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 AA 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 AA, as desired.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.