Competition problem — Combinatorics

Library / /315 of 860

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

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