Question

One commercially available ten-button lock may be opened by depressing—in any order—the correct five buttons. One sample has $\{1,2,3,6,9\}$ as its combination. Suppose that these locks are redesigned so that sets of as many as nine buttons or as few as one button could serve as combinations. How many additional combinations would this allow?

Answer

Answer: 770

Concepts:combinations subsets complementary counting

Difficulty rating: 1630

Small Hint:

Count all nonempty proper subsets of the ten buttons

Big Hint:

Subtract the five-button combinations that the original design already allowed

Solution:

The redesigned lock permits every nonempty subset except the full set, giving $2^{10}-2=1022$ combinations. The original lock permits $\binom{10}{5}=252.$ Thus the number of additional combinations is $1022-252=770.$

1988 AIME Problem 1

Answer: 770

Difficulty rating: 1630

Small Hint:

Big Hint:

Solution:

Problem 1 in Other Years