Competition problem — Combinatorics

Library / /42 of 156

Combinatorics Difficulty 4.2 AIME Find the answer China

Suppose set $S = \{1, 2, 3, \dots, 10\}$ and the subset $A$ of $S$ satisfies

$A \cap \{1, 2, 3\} \neq \emptyset, \quad A \cup \{4, 5, 6\} \neq S.$
The number of such subsets is ________.

Your answer

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

Solution

First, we will find the number $N_1$ of subsets $A$ of $S$ such that $A \cap \{1, 2, 3\} \neq \emptyset$ holds.
There are $2^3 - 1 = 7$ ways of selecting at least one element in $1, 2, 3$ , while for each number in $4, 5, \dots, 10$ there are two choices (selected or not selected). Therefore, $N_1 = 7 \times 2^7 = 896$ .

Furthermore, we need to deduct the number of selections $N_2$ which makes $A \cup \{4, 5, 6\} = S$ hold. Of these selections of $A$ , $1, 2, 3, 7, 8, 9, 10$ are all selected. And each of $4, 5, 6$ has two choices (selected or not selected), so $N_2 = 2^3 = 8$ .

Therefore, the number of subsets $A$ satisfying the conditions is $N_1 - N_2 = 896 - 8 = 888$ . $\square$

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.