Maths Olympiad Prep

Library / /275 of 860

Combinatorics Difficulty 5.0 AIME, harder Find the answer

Let An={a1,a2,a3,,an,b}A_{n}=\{a_{1}, a_{2}, a_{3}, \ldots, a_{n}, b\}, for n3n \geq 3, and let CnC_{n} be the 2-configuration consisting of {ai,ai+1} \{a_{i}, a_{i+1}\} for all 1in1,{a1,an} 1 \leq i \leq n-1, \{a_{1}, a_{n}\} , and {ai,b} \{a_{i}, b\} for 1in 1 \leq i \leq n . Let Se(n)S_{e}(n) be the number of subsets of CnC_{n} that are consistent of order ee. Find Se(101)S_{e}(101) for e=1,2e=1,2, and 3.

A number or a short expression. Spacing and $ signs are ignored.

Solution

For convenience, we assume the ai a_{i} are indexed modulo 101, so that ai+1=a1 a_{i+1}=a_{1} when ai=a101 a_{i}=a_{101} . In any consistent subset of C101 C_{101} of order 1, b b must be paired with exactly one ai a_{i} , say a1 a_{1} . Then, a2 a_{2} cannot be paired with a1 a_{1} , so it must be paired with a3 a_{3} , and likewise we find we use the pairs {a4,a5},{a6,a7},,{a100,a101} \{a_{4}, a_{5}\}, \{a_{6}, a_{7}\}, \ldots, \{a_{100}, a_{101}\} - and this does give us a consistent subset of order 1. Similarly, pairing b b with any other ai a_{i} would give us a unique extension to a consistent configuration of order 1. Thus, we have one such 2-configuration for each i i , giving S1(101)=101 S_{1}(101)=101 altogether. In a consistent subset of order 2, b b must be paired with two other elements. Suppose one of them is ai a_{i} . Then ai a_{i} is also paired with either ai1 a_{i-1} or ai+1 a_{i+1} , say ai+1 a_{i+1} . But then ai1 a_{i-1} needs to be paired up with two other elements, and ai a_{i} is not available, so it must be paired with ai2 a_{i-2} and b b . Now b b has its two pairs determined, so nothing else can be paired with b b . Thus, for ji1,i j \neq i-1, i , we have that aj a_{j} must be paired with aj1 a_{j-1} and aj+1 a_{j+1} . So our subset must be of the form {{b,ai},{ai,ai+1},{ai+1,ai+2},,{a101,a1},,{ai2,ai1},{ai1,b}} \{\{b, a_{i}\}, \{a_{i}, a_{i+1}\}, \{a_{i+1}, a_{i+2}\}, \ldots, \{a_{101}, a_{1}\}, \ldots, \{a_{i-2}, a_{i-1}\}, \{a_{i-1}, b\}\} for some i i . On the other hand, for any i=1,,101 i=1, \ldots, 101 , this gives a subset meeting our requirements. So, we have 101 possibilities, and S2(101)=101 S_{2}(101)=101 . Finally, in a consistent subset of order 3, each ai a_{i} must be paired with ai1,ai+1 a_{i-1}, a_{i+1} , and b b . But then b b occurs in 101 pairs, not just 3, so we have a contradiction. Thus, no such subset exists, so S3(101)=0 S_{3}(101)=0 .

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.