Question

设 $B$ 为所有二进制整数的集合，这些整数恰好由 $5$ 个零和 $8$ 个一写成，允许前导零。对 $B$ 中两个元素做所有可能的减法，即用一个元素减去另一个元素。求结果为 $1$ 的次数。

Let $B$ be the set of all binary integers that can be written using exactly $5$ zeros and $8$ ones where leading zeros are allowed. If all possible subtractions are performed in which one element of $B$ is subtracted from another, find the number of times the answer $1$ is obtained.

答案

答案：330

知识点：进制组合

难度评级：2460

小提示：

数出 $m$ 和 $m + 1$ 都属于 $B$ 的数对。加 $1$ 会把末尾形如 $011\ldots1$ 的块变成 $100\ldots0$ 。

Count pairs $m$ and $m + 1$ that are both in $B.$ Adding $1$ turns a trailing block $011\ldots1$ into $100\ldots0.$

大提示：

只有当 $m$ 以 $01$ 结尾时，一的个数才不变；前面的十一个数字相同，且含有七个一和四个零

The number of ones is unchanged only when $m$ ends in $01;$ the other eleven digits are shared and contain seven ones and four zeros

解答：

我们要数 $B$ 中相差 $1$ 的数对，也就是数 $m$ 和 $m + 1$ 都在该集合中的数对。给二进制数加 $1$ 会把末尾的 $011\cdots1$ （一个零后跟 $k$ 个一）变成 $100\cdots0$ ，使一的个数改变 $1 - k$ 。两个数都恰有八个一，当且仅当 $k = 1$ ：此时 $m$ 以 $01$ 结尾， $m + 1$ 以 $10$ 结尾，且两数在其他位置完全相同。

共同的前十一个数字于是由剩下的七个一和四个零组成。由于允许前导零，每种排列都给出一个有效数对，共有 $\binom{11}{4} = 330$ 个。每个数对恰好产生一次结果 $1$ ，所以次数为 $330$ 。

We must count pairs of elements of $B$ differing by $1,$ say $m$ and $m + 1.$ Adding $1$ to a binary number turns its trailing block $011\cdots1$ (a zero followed by $k$ ones) into $100\cdots0,$ changing the number of ones by $1 - k.$ Both numbers have exactly eight ones precisely when $k = 1:$ $m$ ends in $01,$ $m + 1$ ends in $10,$ and the two numbers agree everywhere else.

The shared first eleven digits then consist of the remaining seven ones and four zeros, and since leading zeros are allowed, every arrangement gives a valid pair: $\binom{11}{4} = 330.$ Each pair produces the answer $1$ exactly once, so the count is $330.$

2012 AIME I 第 5 题

答案：330

难度评级：2460

小提示：

大提示：

解答：

其他年份的第 5 题