Question

有一种市售的十按钮锁，只要以任意顺序按下正确的五个按钮即可打开。某把锁的密码为 $\{1,2,3,6,9\}$ 。现将这种锁重新设计，使一至九个按钮组成的集合都可作为密码。这样会增加多少种密码？

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?

答案

答案：770

知识点：组合子集补集计数

难度评级：1630

小提示：

计算十个按钮的所有非空真子集

Count all nonempty proper subsets of the ten buttons

大提示：

减去原设计已经允许的五按钮密码

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

解答：

新设计允许除全集外的每个非空子集，共有 $2^{10}-2=1022$ 种密码。原设计允许 $\binom{10}{5}=252$ 种。因此增加的密码数为 $1022-252=770$ 。

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 第 1 题

答案：770

难度评级：1630

小提示：

大提示：

解答：

其他年份的第 1 题