Maths Olympiad Prep

Library / /688 of 860

Combinatorics Difficulty 5.4 AIME, harder Find the answer

Let A={a1,b1,a2,b2,,a10,b10}A=\{a_{1}, b_{1}, a_{2}, b_{2}, \ldots, a_{10}, b_{10}\}, and consider the 2-configuration CC consisting of {ai,bi} \{a_{i}, b_{i}\} for all 1i10,{ai,ai+1} 1 \leq i \leq 10, \{a_{i}, a_{i+1}\} for all 1i9 1 \leq i \leq 9 , and {bi,bi+1} \{b_{i}, b_{i+1}\} for all 1i9 1 \leq i \leq 9 . Find the number of subsets of CC that are consistent of order 1.

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

Solution

Let An={a1,b1,a2,b2,,an,bn} A_{n}=\{a_{1}, b_{1}, a_{2}, b_{2}, \ldots, a_{n}, b_{n}\} for n1 n \geq 1 , and consider the 2-configuration Cn C_{n} consisting of {ai,bi} \{a_{i}, b_{i}\} for all 1in,{ai,ai+1} 1 \leq i \leq n, \{a_{i}, a_{i+1}\} for all 1in1 1 \leq i \leq n-1 , and {bi,bi+1} \{b_{i}, b_{i+1}\} for all 1in1 1 \leq i \leq n-1 . Let Nn N_{n} be the number of subsets of Cn C_{n} that are consistent of order 1 (call these "matchings" of Cn C_{n} ). Consider any matching of Cn+2 C_{n+2} . Either an+2 a_{n+2} is paired with bn+2 b_{n+2} , in which case the remaining elements of our matching form a matching of Cn+1 C_{n+1} ; or an+2 a_{n+2} is paired with an+1 a_{n+1} , in which case bn+2 b_{n+2} must be paired with bn+1 b_{n+1} , and the remaining elements form a matching of Cn C_{n} . It follows that Nn+2=Nn+1+Nn N_{n+2}=N_{n+1}+N_{n} . By direct calculation, N1=1 N_{1}=1 and N2=2 N_{2}=2 , and now computing successive values of Nn N_{n} using the recurrence yields N10=89 N_{10}=89 .

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.