Competition problem — Combinatorics

Library / /272 of 520

Combinatorics Difficulty 5.3 AIME, harder Find the answer

1. Let $m, n \in \mathbf{N}_{+}$ , and $m>n$ , sets $A, B, C$ satisfy
$\begin{array}{l} A=\{1,2, \cdots, m\}, B=\{1,2, \cdots, n\}, \\ C \subseteq A, B \cap C \neq \varnothing . \end{array}$

Then the number of sets $C$ that meet the conditions is $\qquad$

Your answer

A number or a short expression. Spacing and $ signs are ignored.

Solution

$-1.2^{m-n}\left(2^{n}-1\right) \text {. }$

From the condition, we know that the elements of set $C$ partly come from the non-empty subsets of set $B$ , which have $2^{n}-1$ ways of selection; the other part comes from the set $\{n+1, n+2, \cdots, m\}$ , which has $2^{m-n}$ ways of selection. Therefore, there are a total of $2^{m-n}\left(2^{n}-1\right)$ ways of selection.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.