2021 AIME I 第 3 题

Question

求小于

1000

且可以表示为两个

2

的整数次幂之差的正整数个数。

Find the number of positive integers less than

1000

that can be expressed as the difference of two integral powers of

2.

答案

答案：50

知识点：2的幂因式分解分类讨论

难度评级：2110

小提示：

每个这样的差都可写成

2^b(2^c - 1)

，其中

c \ge 1

，并且它的奇数部分

2^c - 1

会确定

c

Every such difference is

2^b(2^c - 1)

with

c \ge 1,

and its odd part

2^c - 1

identifies

c

大提示：

不同的数对

(b, c)

给出不同的值，所以对每个

c

分别统计小于

1000

的值。注意：

63 \cdot 16 = 1008

会打破前面的模式。

Distinct pairs

(b, c)

give distinct values, so count values below

1000

for each

c

separately. Beware:

63 \cdot 16 = 1008

breaks the pattern.

解答：

两个

2

的幂之差为

2^a - 2^b = 2^b(2^c - 1)

，其中

c = a - b \ge 1

。因为

2^c - 1

是奇数，所以该数的奇数部分确定

c

，而

2

的幂次部分确定

b

，因此不同的数对

(b, c)

会给出不同整数。只需统计满足

2^b(2^c - 1) \lt 1000

的数对。

对

c = 1, 2, \ldots, 9

，因子

2^c - 1

分别为

1, 3, 7, 15, 31, 63, 127, 255, 511

，允许的

b

的个数分别为

10, 9, 8, 7, 6, 4, 3, 2, 1

（

63

的计数降为

4

，因为

63 \cdot 16 = 1008 \gt 1000

，而

31 \cdot 32 = 992

仍然符合）。

总数为

10 + 9 + 8 + 7 + 6

+ 4 + 3 + 2 + 1 = 50

。

A difference of powers of

2

is

2^a - 2^b = 2^b(2^c - 1)

where

c = a - b \ge 1.

Since

2^c - 1

is odd, the odd part of the number determines

c

and the power of

2

determines

b,

so distinct pairs

(b, c)

yield distinct integers. It suffices to count pairs with

2^b(2^c - 1) \lt 1000.

For

c = 1, 2, \ldots, 9

the factor

2^c - 1

is

1, 3, 7, 15, 31, 63, 127, 255, 511,

and the number of allowed values of

b

is

10, 9, 8, 7, 6, 4, 3, 2, 1

respectively (the count for

63

drops to

4

because

63 \cdot 16 = 1008 \gt 1000,

while

31 \cdot 32 = 992

still fits).

The total is

10 + 9 + 8 + 7 + 6

+ 4 + 3 + 2 + 1 = 50.

2021 AIME I 第 3 题

答案：50

难度评级：2110

小提示：

大提示：

解答：

其他年份的第 3 题