Competition problem — Combinatorics

Library / /316 of 841

Combinatorics Difficulty 5.1 AIME, harder Find the answer

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$ .

Your answer

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

Solution

968. 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: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.