Question

对正整数 $n$ ，用 $D(n)$ 表示 $n$ 的二进制表示中相邻且不同的数字对的个数。例如， $D(3)=D(11_2)=0$ 、 $D(21)=D(10101_2)=4$ 、 $D(97)=D(1100001_2)=2$ 。有多少个不超过 $97$ 的正整数 $n$ 满足 $D(n)=2$ ？

For positive integers $n,$ denote by $D(n)$ the number of pairs of different adjacent digits in the binary (base two) representation of $n.$ For example, $D(3)=D(11_2)=0,$ $D(21)=D(10101_2)=4,$ and $D(97)=D(1100001_2)=2.$ For how many positive integers $n$ less than or equal to $97$ does $D(n)=2?$

$16$

$20$

$26$

$30$

$35$

答案：C

知识点：binary representation 组合

难度评级：2290

小提示：

符合条件的二进制数由一段 $1$ 、一段 $0$ 、再一段 $1$ 组成

A valid binary numeral consists of a block of $1$ s, then $0$ s, then $1$ s

大提示：

按位数统计三至六位的情况，再单独处理七位数的上界 $97=1100001_2$

Count by bit length through six bits, then handle the seven-bit cutoff $97=1100001_2$ separately

解答：

一个恰好发生两次数字变化的 $d$ 位二进制数必为 $1^a0^b1^c$ 的形式，其中 $a$ 、 $b$ 、 $c$ 均为正整数，因此共有 $\binom{d-1}{2}$ 种。对 $d=3$ 、 $d=4$ 、 $d=5$ 、 $d=6$ ，总数为 $1+3+6+10=20$ 。在不超过 $1100001_2=97$ 的七位数中，以单个 $1$ 开头的五种形式都符合条件；以至少两个 $1$ 开头的形式中，只有 $1100001_2$ 本身符合上界。因此共有 $20+6=26$ 个，正确答案是 C。

A $d$ -bit numeral with exactly two changes has form $1^a0^b1^c$ with positive $a,$ $b,$ $c,$ giving $\binom{d-1}{2}$ choices. For $d=3,$ $d=4,$ $d=5,$ $d=6,$ the total is $1+3+6+10=20.$ Among seven-bit numbers at most $1100001_2=97,$ the five forms beginning with one $1$ all work, and the only form beginning with at least two $1$ s is $1100001_2$ itself. Thus there are $20+6=26,$ and C is correct.

1997 AMC 12 第 30 题

答案：C

难度评级：2290

小提示：

大提示：

解答：

其他年份的第 30 题