Maths Olympiad Prep

Track / Stage 4 / 336 of 340 #596 of 1964

Problem 596

AMC 12 late, AIME early
Combinatorics Difficulty 5.0 Find the answer

The number of sets AA that satisfy {a,b}A{a,b,c,d}\{a, b\} \subseteq A \varsubsetneqq \{a, b, c, d\} is \qquad.

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

Next problem →

Official solution

The number of sets AA that satisfy the condition is 221=32^{2}-1=3.
Key to the solution The essence of this example is to find the number of proper subsets of the set {c,d}\{c, d\}; generally, if n,kNn, k \in \mathbf{N}, k<nk<n, then the number of sets AA that satisfy {a1,a2,,ak}A{a1,a2,,an}\left\{a_{1}, a_{2}, \cdots, a_{k}\right\} \subseteq A \varsubsetneqq\left\{a_{1}, a_{2}, \cdots, a_{n}\right\} is 2nk12^{n-k}-1.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.