2009 UNCO Math Contest II Problems/Problem 10

Problem

Let $S=\left \{1,2,3,\ldots ,n\right \}$ . Determine the number of subsets $A$ of $S$ such that $A$ contains at least two elements and such that no two elements of $A$ differ by $1$ when

(a) $n=10$

(b) $n=20$

(c) generalize for any $n$ .

Solution

(a) $133$

(b) $\binom{19}{2}+\binom{18}{3}+\binom{17}{4}+\cdots \binom{11}{10}$

(c) $\binom{n-1}{2}+\binom{n-2}{3}+\binom{n-3}{4}+\cdots$

2009 UNCO Math Contest II (Problems • Answer Key • Resources)
Preceded by Problem 9	Followed by Problem 11
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10
All UNCO Math Contest Problems and Solutions

Page

Toolbox

Search

2009 UNCO Math Contest II Problems/Problem 10

Problem

Solution

See also