AMC12 2013 B

AMC12 2013 B · Q23

AMC12 2013 B · Q23. It mainly tests Basic counting (rules of product/sum), Remainders & modular arithmetic.

Bernardo chooses a three-digit positive integer $N$ and writes both its base-5 and base-6 representations on a blackboard. Later LeRoy sees the two numbers Bernardo has written. Treating the two numbers as base-10 integers, he adds them to obtain an integer $S$. For example, if $N=749$, Bernardo writes the numbers $10{,}444$ and $3{,}245$, and LeRoy obtains the sum $S=13{,}689$. For how many choices of $N$ are the two rightmost digits of $S$, in order, the same as those of $2N$?

伯纳多选择一个三位正整数 $N$，并把它的五进制表示和六进制表示都写在黑板上。后来勒罗伊看到了伯纳多写下的两个数。他把这两个数都当作十进制整数相加，得到整数 $S$。例如，当 $N=749$ 时，伯纳多写下 $10{,}444$ 和 $3{,}245$，勒罗伊算得 $S=13{,}689$。问有多少个 $N$ 的取值，使得 $S$ 的最右边两位数字（按顺序）与 $2N$ 的最右边两位数字相同？

(A) 5 5

(B) 10 10

(D) 20 20

(E) 25 25

Answer

Correct choice: (E)

正确答案：（E）

Solution

Answer (E): Expand the set of three-digit positive integers to include integers $N$, $0 \le N \le 99$, with leading zeros appended. Because $\mathrm{lcm}(5^2,6^2,10^2)=900$, such an integer $N$ meets the required condition if and only if $N+900$ does. Therefore $N$ can be considered to be chosen from the set of integers between $000$ and $899$, inclusive. Suppose that the last two digits in order of the base-5 representation of $N$ are $a_1$ and $a_0$. Similarly, suppose that the last two digits of the base-6 representation of $N$ are $b_1$ and $b_0$. By assumption, $2N \equiv a_0+b_0 \pmod{10}$, but $N \equiv a_0 \pmod{5}$ and so $$ a_0+b_0 \equiv 2N \equiv 2a_0 \pmod{10}. $$ Thus $a_0 \equiv b_0 \pmod{10}$ and because $0 \le a_0 \le 4$ and $0 \le b_0 \le 5$, it follows that $a_0=b_0$. Because $N \equiv a_0 \pmod{5}$, it follows that there is an integer $N_1$ such that $N=5N_1+a_0$. Also, $N \equiv a_0 \pmod{6}$ implies that $5N_1+a_0 \equiv a_0 \pmod{6}$ and so $N_1 \equiv 0 \pmod{6}$. It follows that $N_1=6N_2$ for some integer $N_2$ and so $N=30N_2+a_0$. Similarly, $N \equiv 5a_1+a_0 \pmod{25}$ implies that $30N_2+a_0 \equiv 5a_1+a_0 \pmod{25}$ and then $N_2 \equiv 6N_2 \equiv a_1 \pmod{5}$. It follows that $N_2=5N_3+a_1$ for some integer $N_3$ and so $N=150N_3+30a_1+a_0$. Once more, $N \equiv 6b_1+a_0 \pmod{36}$ implies that $6N_3-6a_1+a_0 \equiv 150N_3+30a_1+a_0 \equiv 6b_1+a_0 \pmod{36}$ and then $N_3 \equiv a_1+b_1 \pmod{6}$. It follows that $N_3=6N_4+a_1+b_1$ for some integer $N_4$ and so $N=900N_4+180a_1+150b_1+a_0$. Finally, $2N \equiv 10(a_1+b_1)+2a_0 \pmod{100}$ implies that $$ 60a_1+2a_0 \equiv 360a_1+300b_1+2a_0 \equiv 10a_1+10b_1+2a_0 \pmod{100}. $$ Therefore $5a_1 \equiv b_1 \pmod{10}$, equivalently, $b_1 \equiv 0 \pmod{5}$ and $a_1 \equiv b_1 \pmod{2}$. Conversely, if $N=900N_4+180a_1+150b_1+a_0$, $a_0=b_0$, and $5a_1 \equiv b_1 \pmod{10}$, then $2N \equiv 60a_1+2a_0 =10(a_1+5a_1)+a_0+b_0 \equiv 10(a_1+b_1)+(a_0+b_0) \pmod{100}$. Because $0 \le a_1 \le 4$ and $0 \le b_1 \le 5$, it follows that there are exactly $5$ different pairs $(a_1,b_1)$, namely $(0,0)$, $(2,0)$, $(4,0)$, $(1,5)$, and $(3,5)$. Each of these can be combined with $5$ different values of $a_0$ ($0 \le a_0 \le 4$), to determine exactly $25$ different numbers $N$ with the required property.

解答（E）：将三位正整数的集合扩展为包含整数 $N$（$0 \le N \le 99$），并在前面补零。因为 $\mathrm{lcm}(5^2,6^2,10^2)=900$，这样的整数 $N$ 满足所需条件当且仅当 $N+900$ 也满足。因此可以认为 $N$ 从 $000$ 到 $899$（含端点）的整数中选取。设 $N$ 的五进制表示中按顺序最后两位为 $a_1$ 和 $a_0$。同样地，设 $N$ 的六进制表示中最后两位为 $b_1$ 和 $b_0$。由题设，$2N \equiv a_0+b_0 \pmod{10}$，但 $N \equiv a_0 \pmod{5}$，因此 $$ a_0+b_0 \equiv 2N \equiv 2a_0 \pmod{10}. $$ 于是 $a_0 \equiv b_0 \pmod{10}$，又因为 $0 \le a_0 \le 4$ 且 $0 \le b_0 \le 5$，可得 $a_0=b_0$。由于 $N \equiv a_0 \pmod{5}$，存在整数 $N_1$ 使得 $N=5N_1+a_0$。另外，$N \equiv a_0 \pmod{6}$ 推出 $5N_1+a_0 \equiv a_0 \pmod{6}$，从而 $N_1 \equiv 0 \pmod{6}$。因此对某个整数 $N_2$ 有 $N_1=6N_2$，于是 $N=30N_2+a_0$。类似地，$N \equiv 5a_1+a_0 \pmod{25}$ 推出 $30N_2+a_0 \equiv 5a_1+a_0 \pmod{25}$，进而 $N_2 \equiv 6N_2 \equiv a_1 \pmod{5}$。因此对某个整数 $N_3$ 有 $N_2=5N_3+a_1$，于是 $N=150N_3+30a_1+a_0$。再进一步，$N \equiv 6b_1+a_0 \pmod{36}$ 推出 $6N_3-6a_1+a_0 \equiv 150N_3+30a_1+a_0 \equiv 6b_1+a_0 \pmod{36}$，从而 $N_3 \equiv a_1+b_1 \pmod{6}$。因此对某个整数 $N_4$ 有 $N_3=6N_4+a_1+b_1$，于是 $N=900N_4+180a_1+150b_1+a_0$。最后，$2N \equiv 10(a_1+b_1)+2a_0 \pmod{100}$ 蕴含 $$ 60a_1+2a_0 \equiv 360a_1+300b_1+2a_0 \equiv 10a_1+10b_1+2a_0 \pmod{100}. $$ 因此 $5a_1 \equiv b_1 \pmod{10}$；等价地，$b_1 \equiv 0 \pmod{5}$ 且 $a_1 \equiv b_1 \pmod{2}$。反过来，若 $N=900N_4+180a_1+150b_1+a_0$、$a_0=b_0$ 且 $5a_1 \equiv b_1 \pmod{10}$，则 $2N \equiv 60a_1+2a_0 =10(a_1+5a_1)+a_0+b_0 \equiv 10(a_1+b_1)+(a_0+b_0) \pmod{100}$。由于 $0 \le a_1 \le 4$ 且 $0 \le b_1 \le 5$，可知恰有 $5$ 对不同的 $(a_1,b_1)$，分别为 $(0,0)$、$(2,0)$、$(4,0)$、$(1,5)$、$(3,5)$。每一对又可与 $5$ 个不同的 $a_0$ 取值（$0 \le a_0 \le 4$）组合，从而得到恰好 $25$ 个满足所需性质的不同整数 $N$。

Topics