Olympiad Maths Prep

Track / Stage 3 / 21 of 260 #21 of 2000

Problem 21

AMC 10/12, early questions
Combinatorics Difficulty 3.0 Find the answer

For sets AA and BB, let card(A)card(A) represent the number of elements in the finite set AA. Given card(A)=Mcard(A) = M and card(B)=Ncard(B) = N (M<N)(M < N), and set CC satisfies ACBA \subseteq C \subseteq B, the number of sets CC that meet the conditions is ______.

Official solution

Given card(A)=Mcard(A) = M and card(B)=Ncard(B) = N with M<NM < N, and considering ACBA \subseteq C \subseteq B, we aim to find the number of possible sets CC.

1. **Identify the relationship between AA and BB**: Since ABA \subseteq B, every element of AA is also an element of BB. This implies card(BA)=NMcard(\complement_{B}A) = N - M, where BA\complement_{B}A represents the elements in BB that are not in AA.

2. **Understand the constraints on CC**: The condition ACBA \subseteq C \subseteq B means that CC must include all elements of AA and may include any (including none or all) of the elements from BA\complement_{B}A.

3. **Calculate the number of possible sets CC**: The number of subsets of BA\complement_{B}A (which represents the elements that can be added to AA to form CC) is 2card(BA)=2NM2^{card(\complement_{B}A)} = 2^{N-M}. This is because each element of BA\complement_{B}A can either be included in or excluded from a subset, leading to two choices per element.

Therefore, the number of sets CC that meet the conditions is 2NM2^{N-M}.

Final answer: 2NM\boxed{2^{N-M}}.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.