CombinatoricsDifficulty 4.4AIMEFind the answerUnited States
Problem:
For each positive integer n let Sn denote the set {1,2,3,…,n}. Compute the number of triples of subsets A,B,C of S2006 (not necessarily nonempty or proper) such that A is a subset of B and S2006−A is a subset of C.
A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.
Solution
Solution:
Let Ao,Bo,Co be sets satisfying the said conditions. Note that 1∈Ao implies that 1∈Bo and 1∈/S2006−Ao so that 1 may or may not be in Co. Also, 1∈/Ao implies that 1∈S2006−Ao⊂Co while 1 may or may not be in Bo. Thus there are four possibilities for the distribution of 1, and since the same argument holds independently for 2,3,…,2006, the answer is 42006 or 24012.
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.