Question

令 $S$ 为所有二进制表示中恰好有 $8$ 个一的正整数按递增顺序排列成的数列。令 $N$ 为 $S$ 中第 $1000$ 个数。求 $N$ 除以 $1000$ 的余数。

Let $S$ be the increasing sequence of positive integers whose binary representation has exactly $8$ ones. Let $N$ be the $1000$ th number in $S.$ Find the remainder when $N$ is divided by $1000.$

答案

答案：32

知识点：进制组合系统列举

难度评级：2790

解答：

小于 $2^{12}$ 的 $S$ 中元素有 $\binom{12}{8} = 495$ 个，小于 $2^{13}$ 的有 $\binom{13}{8} = 1287$ 个，所以 $N$ 的二进制表示有 $13$ 位，并且小于 $2^{13}$ 且大于它的元素有 $1287 - 1000 = 287$ 个。二进制表示以 $11$ 开头的 $\binom{11}{6} = 462$ 个元素是最大的那些，所以 $N$ 以 $11$ 开头，并且是其中第 $462 - 287 = 175$ 小的数。

在这些数中，以 $1100$ 开头的有 $\binom{9}{6} = 84$ 个，接下来以 $11010$ 开头的有 $\binom{8}{5} = 56$ 个，再接下来以 $110110$ 开头的有 $\binom{7}{4} = 35$ 个。由于 $84 + 56 + 35 = 175$ ，数 $N$ 是以 $110110$ 开头的最大元素，也就是二进制数 $1101101111000$ 。

它的值为 $2^{12} + 2^{11} + 2^9 + 2^8$ $+ 2^6 + 2^5 + 2^4 + 2^3 = 7032$ ，所以除以 $1000$ 的余数是 $32$ 。

There are $\binom{12}{8} = 495$ members of $S$ below $2^{12}$ and $\binom{13}{8} = 1287$ below $2^{13},$ so $N$ has $13$ binary digits, and exactly $1287 - 1000 = 287$ members below $2^{13}$ exceed it. The $\binom{11}{6} = 462$ members whose binary representations begin $11$ are the largest ones, so $N$ begins with $11$ and is the $462 - 287 = 175$ th smallest of them.

Among these, $\binom{9}{6} = 84$ begin $1100,$ the next $\binom{8}{5} = 56$ begin $11010,$ and the next $\binom{7}{4} = 35$ begin $110110.$ Since $84 + 56 + 35 = 175,$ the number $N$ is the largest member beginning $110110,$ namely $1101101111000$ in binary.

Its value is $2^{12} + 2^{11} + 2^9 + 2^8$ $+ 2^6 + 2^5 + 2^4 + 2^3 = 7032,$ so the remainder upon division by $1000$ is $32.$

2012 AIME II 第 7 题

答案：32

难度评级：2790

解答：

其他年份的第 7 题