Let , for , and let be the 2-configuration consisting of for all , and for . Let be the number of subsets of that are consistent of order . Find for , and 3.
Solution
For convenience, we assume the are indexed modulo 101, so that when . In any consistent subset of of order 1, must be paired with exactly one , say . Then, cannot be paired with , so it must be paired with , and likewise we find we use the pairs - and this does give us a consistent subset of order 1. Similarly, pairing with any other would give us a unique extension to a consistent configuration of order 1. Thus, we have one such 2-configuration for each , giving altogether. In a consistent subset of order 2, must be paired with two other elements. Suppose one of them is . Then is also paired with either or , say . But then needs to be paired up with two other elements, and is not available, so it must be paired with and . Now has its two pairs determined, so nothing else can be paired with . Thus, for , we have that must be paired with and . So our subset must be of the form for some . On the other hand, for any , this gives a subset meeting our requirements. So, we have 101 possibilities, and . Finally, in a consistent subset of order 3, each must be paired with , and . But then occurs in 101 pairs, not just 3, so we have a contradiction. Thus, no such subset exists, so .