Question

Let $m$ be the number of five-element subsets that can be chosen from the set of the first $14$ natural numbers so that at least two of the five numbers are consecutive. Find the remainder when $m$ is divided by $1000.$

Answer

Answer: 750

Concepts:complementary counting bijection subsets

Difficulty rating: 2300

Solution:

Count the complement: subsets $a_1 \lt a_2 \lt a_3 \lt a_4 \lt a_5$ with no two consecutive. Setting $b_i = a_i - (i - 1)$ turns each such subset into five distinct numbers $b_1 \lt b_2 \lt \cdots \lt b_5$ in $\{1, \ldots, 10\},$ and this map is reversible, so there are $\binom{10}{5} = 252$ subsets with no two consecutive numbers.

Therefore $m = \binom{14}{5} - \binom{10}{5}$ $= 2002 - 252 = 1750,$ and the remainder upon division by $1000$ is $750.$

2009 AIME II Problem 6

Answer: 750

Difficulty rating: 2300

Solution:

Problem 6 in Other Years