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 22−1=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,k∈Nn, 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 2n−k−12^{n-k}-1.

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