Maths Olympiad Prep

Library / /604 of 860

Combinatorics Difficulty 5.3 AIME, harder Find the answer

Let A={V,W,X,Y,Z,v,w,x,y,z}A=\{V, W, X, Y, Z, v, w, x, y, z\}. Find the number of subsets of the 2-configuration {{V,W},{W,X},{X,Y},{Y,Z},{Z,V},{v,x},{v,y},{w,y},{w,z},{x,z},{V,v},{W,w},{X,x},{Y,y},{Z,z}} \{\{V, W\}, \{W, X\}, \{X, Y\}, \{Y, Z\}, \{Z, V\}, \{v, x\}, \{v, y\}, \{w, y\}, \{w, z\}, \{x, z\}, \{V, v\}, \{W, w\}, \{X, x\}, \{Y, y\}, \{Z, z\}\} that are consistent of order 1.

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

Solution

No more than two of the pairs {v,x},{v,y},{w,y},{w,z},{x,z} \{v, x\}, \{v, y\}, \{w, y\}, \{w, z\}, \{x, z\} may be included in a 2-configuration of order 1, since otherwise at least one of v,w,x,y,z v, w, x, y, z would occur more than once. If exactly one is included, say {v,x} \{v, x\} , then w,y,z w, y, z must be paired with W,Y,Z W, Y, Z , respectively, and then V V and X X cannot be paired. So either none or exactly two of the five pairs above must be used. If none, then v,w,x,y,z v, w, x, y, z must be paired with V,W,X,Y,Z V, W, X, Y, Z , respectively, and we have 1 2-configuration arising in this manner. If exactly two are used, we can check that there are 5 ways to do this without duplicating an element: {v,x},{w,y} \{v, x\}, \{w, y\} , {v,x},{w,z} \{v, x\}, \{w, z\} , {v,y},{w,z} \{v, y\}, \{w, z\} , {v,y},{x,z} \{v, y\}, \{x, z\} , {w,y},{x,z} \{w, y\}, \{x, z\} . In each case, it is straightforward to check that there is a unique way of pairing up the remaining elements of A A . So we get 5 2-configurations in this way, and the total is 6.

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.