Competition problem — Combinatorics

Library / /35 of 94

Combinatorics Difficulty 4.7 AIME Prove it United States

Problem:

Determine the number of subsets $S$ of $\{1,2,3, \ldots, 10\}$ with the following property: there exist integers $a < b < c$ with $a \in S$ , $b \notin S$ , $c \in S$ .

Solution

Solution:

There are $2^{10} = 1024$ subsets of $\{1,2, \ldots, 10\}$ altogether. Any subset without the specified property must be either the empty set or a block of consecutive integers. To specify a block of consecutive integers, we either have just one element (10 choices) or a pair of distinct endpoints $\left(\binom{10}{2} = 45\right.$ choices $)$ . So the number of sets with our property is $1024 - (1 + 10 + 45) = 968$ .

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.