Difference between revisions of "2002 AIME II Problems/Problem 9"
Line 14: | Line 14: | ||
[[Category:Intermediate Combinatorics Problems]] | [[Category:Intermediate Combinatorics Problems]] | ||
+ | {{MAA Notice}} |
Revision as of 20:37, 4 July 2013
Problem
Let be the set
Let
be the number of sets of two non-empty disjoint subsets of
. (Disjoint sets are defined as sets that have no common elements.) Find the remainder obtained when
is divided by
.
Solution
Let the two disjoint subsets be and
, and let
. For each
, either
,
, or
. So there are
ways to organize the elements of
into disjoint
,
, and
.
However, there are ways to organize the elements of
such that
and
, and there are
ways to organize the elements of
such that
and
.
But, the combination such that
and
is counted twice.
Thus, there are ordered pairs of sets
. But since the question asks for the number of unordered sets
,
.
See also
2002 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 8 |
Followed by Problem 10 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.