2010 AIME II Problem 8

Below is the professionally curated solution for Problem 8 of the 2010 AIME II, from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2010 AIME II solutions, or check the answer key.

All of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:subsetscombinationscomplementary counting

Difficulty rating: 2520

8.

Let NN be the number of ordered pairs of nonempty sets A\mathcal{A} and B\mathcal{B} that have the following properties: • AB={1,2,3,4,5,6,7,8,9,10,11,12},\mathcal{A} \cup \mathcal{B} = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12\},AB=,\mathcal{A} \cap \mathcal{B} = \emptyset, • the number of elements of A\mathcal{A} is not an element of A,\mathcal{A}, • the number of elements of B\mathcal{B} is not an element of B.\mathcal{B}. Find N.N.

Solution:

Let k=A,k = |\mathcal{A}|, so B=12k|\mathcal{B}| = 12 - k with 1k11.1 \le k \le 11. Since every element lies in exactly one set, kAk \notin \mathcal{A} means kB,k \in \mathcal{B}, and 12kB12 - k \notin \mathcal{B} means 12kA.12 - k \in \mathcal{A}. If k=6,k = 6, then 66 would have to belong to both sets, which is impossible, so k6.k \ne 6.

For each other k,k, the elements kk and 12k12 - k are already placed, and the remaining k1k - 1 elements of A\mathcal{A} can be chosen from the other 1010 numbers in (10k1)\binom{10}{k-1} ways, with B\mathcal{B} taking the rest. Hence N=k=111(10k1)(105)=210252=772.N = \sum_{k=1}^{11} \binom{10}{k-1} - \binom{10}{5} = 2^{10} - 252 = 772.

← Problem 7Full ExamProblem 9

Problem 8 in Other Years