Competition problem — Combinatorics

Library / /132 of 841

Combinatorics Difficulty 4.9 AIME Find the answer

Find the number of subsets $S$ of $\{1,2, \ldots 63\}$ the sum of whose elements is 2008.

Your answer

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

Solution

Note that $1+2+\cdots+63=2016$ . So the problem is equivalent to finding the number of subsets of $\{1,2, \cdots 63\}$ whose sum of elements is 8. We can count this by hand: $\{8\},\{1,7\},\{2,6\}$ , $\{3,5\},\{1,2,5\},\{1,3,4\}$ .

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.