今日学段:数论 + 组合(AMC 10 难度)
题目来源:MAA 官方 AMC 10 真题(来源存档:Random Math Wiki 题库,原题见 Art of Problem Solving 维基)
【数论】百次幂模 125 的余数个数
难度: ⭐⭐⭐⭐(2024 AMC 10 第 18 题)
题目来源: 2024 AMC 10B Problem 18
知识点: 欧拉定理 · 二项式定理 · 剩余类计数
题目:
整数 $N$ 的 100 次幂 $N^{100}$ 除以 125,得到的余数共有多少种不同的可能?
- (A) 1
- (B) 2
- (C) 5
- (D) 25
- (E) 125
解题过程
解法一:按 $N\bmod 5$ 分类 + 二项式定理。
写 $N=5k+r$,$r\in{0,1,2,3,4}$。
- $r=0$: $N=5k$,则 $N^{100}=5^{100}k^{100}$ 含因子 $125$,余数为 $0$。
- $r=1,2,3,4$: 此时 $\gcd(N,5)=1$。先看平方:
(因为 $r^2\equiv 1,4,9,16\equiv \pm1\pmod 5$。)再用二项式定理展开:
\[N^{100}=\left(N^{2}\right)^{50}=(5m\pm 1)^{50}=(5m)^{50}\pm 50(5m)^{49}+\binom{50}{2}(5m)^{48}+\cdots\pm 50(5m)+1\]除最后一项 $1$ 外,每一项都至少含 $5^{3}=125$,故
\[N^{100}\equiv 1\pmod{125}\]结论: 余数只有 $0$ 和 $1$ 两种(例如 $N=5$ 给余 0,$N=1$ 给余 1,都能取到)。
答案:(B) 2
验证(欧拉定理版): $\varphi(125)=125-25=100$,与 125 互素的 $a$ 满足 $a^{100}\equiv 1\pmod{125}$;5 的倍数的 100 次幂必被 125 整除。两种途径同结论。
常见错误
- 以为余数种类就是模数 125 或其因子个数,不看幂次结构。
- 对 $r\ne0$ 只验证 $N=1$ 就断定全是 1,忽略”种类数”还需确认 0 也能出现。
- 二项式展开时漏看”最后一项是 1”,以为余数是别的数。
【组合】五只蜗牛的并列名次
难度: ⭐⭐⭐(2024 AMC 10 第 17 题)
题目来源: 2024 AMC 10B Problem 17
知识点: 分类加法原理 · 捆绑(集团)计数 · 组合数
题目:
5 只蜗牛赛跑,至多有一处并列,但并列可以涉及任意多只蜗牛。例如结果可以是:某只第一;另外三只并列第二;剩下一只第五。问有多少种不同的比赛结果?
- (A) 180
- (B) 361
- (C) 420
- (D) 431
- (E) 720
解题过程
第 1 步:无并列的情形。 5 只全异、全排序:
\[5!=120\]第 2 步:恰有 $k$ 只并列的情形($2\le k\le 5$)。 从 5 只中选并列的 $k$ 只:$\binom{5}{k}$ 种;把这 $k$ 只捆成一个”集团”,与剩下 $5-k$ 只一起构成 $6-k$ 个”参赛单位”排序,共 $(6-k)!$ 种。
第 3 步:分类求和。
\[5!+\binom{5}{2}\cdot 4!+\binom{5}{3}\cdot 3!+\binom{5}{4}\cdot 2!+\binom{5}{5}\cdot 1!\] \[=120+10\cdot 24+10\cdot 6+5\cdot 2+1\cdot 1=120+240+60+10+1=431\]答案:(D) 431
自查: 题目限定”至多一处并列”,故各情形互斥、直接相加即可;$k=5$ 时全体并列只有 1 种结果,$k=4$ 时 4 只并列 + 1 只单独有前后两种位置,对应 $\binom54\cdot 2!=10$,吻合。
常见错误
- 漏掉 $k=5$(全员并列)这一项,得 430。
- 把”并列集团”内部又去排序(并列没有内部次序)。
- 误以为并列必须恰好 2 只,只用 $\binom52\cdot4!$。
评论