AMC10 2013 B

AMC10 2013 B · Q25

AMC10 2013 B · Q25. It mainly tests Rounding & estimation, 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$_5$ and 3,245$_6$, 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 ?

Bernardo 选择一个三位正整数 N，并在黑板上写下其 5 进制和 6 进制表示。后来 LeRoy 看到这两个数，将它们作为 10 进制整数相加得到 S。例如若 N = 749，Bernardo 写 10,444₅ 和 3,245₆，LeRoy 得 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 $\operatorname{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$），并在前面补零。因为 $\operatorname{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_1=6N_2$（某个整数 $N_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