Maths Olympiad Prep

Track / Stage 4 / 324 of 340 #584 of 1964

Problem 584

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

Example 2 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. Spacing and $ signs are ignored.

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 and solution reproduced as published; topic, difficulty and ordering added by this site.