2012 AIME I 第 5 题

先试着解答 2012 AIME I 第 5 题,然后核对你的答案与精心整理的解答,解答来自 LIVE by Po-Shen Loh。你也可以参加完整限时模拟考试、查看全部 2012 AIME I 解答,或核对答案

所有题目均经美国数学协会(MAA)官方合法授权使用。

5.

BB 为所有二元整数的集合,这些整数恰好由 55 个零和 88 个一写成,允许前导零。 对 BB 中两个元素做所有可能的减法,即用一个元素减去另一个元素。求结果为 11 的次数。

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

答案:330
知识点:进制组合
难度评级:2460
解答:

我们要数 BB 中相差 11 的数对,也就是数 mmm+1m + 1 都在该集合中的数对。给二元数加 11 会把末尾的 0111011\cdots1(一个零后跟 kk 个一)变成 1000100\cdots0,使一的个数改变 1k1 - k。两个数都恰有八个一,当且仅当 k=1k = 1:此时 mm0101 结尾,m+1m + 11010 结尾,且两数在其他位置完全相同。

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

We must count pairs of elements of BB differing by 1,1, say mm and m+1.m + 1. Adding 11 to a binary number turns its trailing block 0111011\cdots1 (a zero followed by kk ones) into 1000,100\cdots0, changing the number of ones by 1k.1 - k. Both numbers have exactly eight ones precisely when k=1:k = 1: mm ends in 01,01, m+1m + 1 ends in 10,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: (114)=330.\binom{11}{4} = 330. Each pair produces the answer 11 exactly once, so the count is 330.330.

← 第 4 题#4
完整试卷

其他年份的第 5 题