Maths Olympiad Prep

Library / /31 of 377

Combinatorics Difficulty 4.4 AIME Find the answer United States

Problem:

For each positive integer nn let SnS_{n} denote the set {1,2,3,,n}\{1,2,3, \ldots, n\}. Compute the number of triples of subsets A,B,CA, B, C of S2006S_{2006} (not necessarily nonempty or proper) such that AA is a subset of BB and S2006AS_{2006}-A is a subset of CC.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:

Let Ao,Bo,CoA_{o}, B_{o}, C_{o} be sets satisfying the said conditions. Note that 1Ao1 \in A_{o} implies that 1Bo1 \in B_{o} and 1S2006Ao1 \notin S_{2006}-A_{o} so that 1 may or may not be in CoC_{o}. Also,
1Ao1 \notin A_{o} implies that 1S2006AoCo1 \in S_{2006}-A_{o} \subset C_{o} while 1 may or may not be in BoB_{o}. Thus there are four possibilities for the distribution of 1, and since the same argument holds independently for 2,3,,20062,3, \ldots, 2006, the answer is 420064^{2006} or 240122^{4012}.

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.