← Reading List
🧮 奥数题

奥数每日两题 2026-08-18:Coinland 硬币最大不可凑额 / 除数卷积函数求 f(2023)

奥数题数学AMC10AMC12概率代数

今日学段:概率 + 代数(AMC 10/12 难度)

题目来源:2023 AMC 12B、2023 AMC 12A 真实竞赛真题(MAA / AoPS Wiki 整理,经 GitHub 题库 Dragjon/AIMElab 的 AoPS 解析数据集抓取,题目与官方完全一致)


【概率】Coinland 硬币的最大不可支付金额

难度: ⭐⭐⭐(高中竞赛难度 · 整数拆分 / Frobenius 硬币问题 / 数论与概率思维)

题目来源: 2023 AMC 12B Problem 16

知识点: 硬币问题(Chicken McNugget 定理) · 同余分析 · 奇偶分类 · 整数线性组合

题目:

在 Coinland 这个国家,硬币的面值有 $6$、$10$、$15$ 分三种。设 $x$ 为「无法用这些硬币恰好凑出」的最贵的物品价格(单位:分)。求 $x$ 的各位数字之和。

\[\textbf{(A) }8\qquad\textbf{(B) }10\qquad\textbf{(C) }7\qquad\textbf{(D) }11\qquad\textbf{(E) }9\]

解题过程

目标: 求最大的整数 $x$,使方程 \(6a + 10b + 15c = x \qquad (a,b,c\in \mathbb{Z}_{\ge 0})\) 无非负整数解。

  1. 提取公因数简化。 把方程同除以 $2$(注意 $6a+10b=2(3a+5b)$,而 $15c$ 的奇偶性由 $c$ 决定):
    • 原式可写成 $2(3a+5b) + 15c = x$。
    • 对 $2$ 取模得 $15c \equiv x \pmod{2}$,即 $c \equiv x \pmod{2}$。也就是说 $x$ 是奇数时 $c$ 必须为奇数,$x$ 是偶数时 $c$ 必须为偶数。
  2. 利用两硬币定理(Chicken McNugget)。 对 $3a+5b$ 而言,由于 $\gcd(3,5)=1$,不能表示的最大数是 $(3-1)(5-1)-1=3$… 这里更方便的是:任何 $\ge (3-1)(5-1)=8$ 的整数都能写成 $3a+5b$($a,b\ge0$)。于是:
    • 偶数情形:$x$ 为偶数时取 $c=0$,则 $x=2(3a+5b)$,只要 $3a+5b\ge 8$ 即 $x\ge 16$ 都可表示。
    • 奇数情形:$x$ 为奇数时必须取 $c\ge1$ 且 $c$ 为奇数,最小取 $c=1$,则 $x=2(3a+5b)+15$,只要 $3a+5b\ge 8$ 即 $x\ge 31$ 都可表示。
  3. 合并结论: 所有 $\ge 30$ 的数都能被凑出(偶数从 16 起、奇数从 31 起,覆盖 30 以上全部整数)。

  4. 检验边界 $x=29$: $29$ 是奇数,故 $c$ 必须为奇数;又 $c\ge1$ 且 $15c\le29$,只能 $c=1$。代入得 \(6a+10b = 29-15 = 14 \;\Longrightarrow\; 3a+5b = 7\) 但 $3a+5b=7$ 无非负整数解($b=0\Rightarrow 3a=7$ 不整;$b\ge1\Rightarrow 5b\ge5$,$3a=2$ 不整)。故 $29$ 不可凑出。

  5. 确定最大值: $30$ 及以上全可凑,而 $29$ 不可凑,所以最大不可凑金额 $x=29$。其数字和为 $2+9=\boxed{\textbf{(D) }11}$。

常见错误

  • 直接套两硬币公式 $(6-1)(10-1)-1=44$ 当作答案,忽略了第三枚硬币 $15$ 会大幅降低不可凑的上界。
  • 奇偶性分析漏掉 $c$ 的奇偶必须与 $x$ 一致,导致误判某些奇数可凑。
  • 检验 $29$ 时忽略了 $c$ 必须是奇数且 $c\ge1$,从而错误认为 $c=0$ 也可行。

知识背景

这是经典的「硬币问题 / Frobenius 问题」:给定若干互质面值的硬币,求不能用它们非负整数线性组合表示的最大整数。两硬币情形有显式公式 $(a-1)(b-1)-1$;三枚及以上无通用简单公式,需结合同余与分类讨论。本题的巧思在于先除以公因数、用奇偶把 $15c$ 拆出,再用两硬币定理覆盖大数,最后只需检验少数边界。这类问题训练「整体覆盖 + 边界反例」的数论直觉。(约 180 字)


【代数】除数卷积函数求 $f(2023)$

难度: ⭐⭐⭐⭐(高中竞赛难度 · 积性函数 / 除数卷积 / 强归纳)

题目来源: 2023 AMC 12A Problem 22

知识点: 除数函数求和(Dirichlet 卷积) · 积性函数 · 强归纳 · 质因数分解

题目:

设 $f$ 是定义在正整数上的唯一函数,满足对一切正整数 $n$ 都有 \(\sum_{d\mid n} d\cdot f\!\left(\frac{n}{d}\right)=1\) 求 $f(2023)$ 的值。

\[\textbf{(A) }-1536\qquad\textbf{(B) }96\qquad\textbf{(C) }108\qquad\textbf{(D) }116\qquad\textbf{(E) }144\]

解题过程

思路: 这是形如 $(n\cdot f)(n)=1$ 的 Dirichlet 卷积方程(其中 $1(n)=1$)。先求 $f$ 在素数幂上的值,再证其积性。

  1. $n=1$: 唯一除数是 $1$,代入得 $1\cdot f(1)=1$,故 $f(1)=1$。

  2. 素数 $p$: 除数为 $1,p$,于是 \(f(p) + p\cdot f(1) = 1 \;\Longrightarrow\; f(p) = 1-p.\)

  3. 素数幂 $p^k$(强归纳): 对 $k=1$ 已知 $f(p)=1-p$。假设对所有 $m\le n$ 都有 $f(p^m)=1-p$,看 $p^{n+1}$: \(f(p^{n+1}) + \sum_{i=1}^{n} p^i(1-p) + p^{n+1}f(1) = 1.\) 其中等比和 $\sum_{i=1}^{n}p^i(1-p)=p(1-p^n)$。代入 $f(1)=1$: \(f(p^{n+1}) + p(1-p^n) + p^{n+1} = f(p^{n+1}) + p = 1 \;\Longrightarrow\; f(p^{n+1})=1-p.\) 故对所有 $k\ge1$,$f(p^k)=1-p$。

  4. 积性(两不同素数 $p,q$): 除数有 $1,p,q,pq$, \(f(pq) + p\,f(q) + q\,f(p) + pq\,f(1) = 1.\) 代入 $f(p)=1-p,\;f(q)=1-q,\;f(1)=1$: \(f(pq) + p(1-q) + q(1-p) + pq = 1 \;\Longrightarrow\; f(pq) = (1-p)(1-q) = f(p)f(q).\) 因此 $f$ 是积性函数,即 $f(mn)=f(m)f(n)$(当 $\gcd(m,n)=1$)。

  5. 计算 $f(2023)$: 分解 $2023=7\cdot 17^2$,且 $\gcd(7,17^2)=1$,所以 \(f(2023)=f(7)\cdot f(17^2) = (1-7)\cdot(1-17) = (-6)\cdot(-16) = \boxed{\textbf{(B) }96}.\)


常见错误

  • 把 $f(17^2)$ 误算成 $(1-17)^2=256$,忘记上面已证对任意次幂 $f(p^k)=1-p$(不是平方)。
  • 直接假设 $f$ 积性而未验证,或在验证时漏掉 $pq\cdot f(1)$ 这一项。
  • 质因数分解出错:$2023\neq 7\cdot 289$ 写错,导致 $f(17^2)$ 计算偏差。

知识背景

本题核心是「除数卷积(Dirichlet convolution)」与「积性函数」。方程 $\sum_{d\mid n}d\,f(n/d)=1$ 等价于 $( \mathrm{id}\ast f)(n)=1(n)$,其中 $\mathrm{id}(n)=n$。由 $\mathrm{id}$ 与常数函数 $1$ 均积性,可推出 $f$ 也积性,从而在素数幂上完全确定。这是数论(尤其是莫比乌斯反演、欧拉函数性质)的标准技术,AMC 12 中以「函数方程 + 归纳 + 分解」的形式考察,是训练抽象代数思维的优质题型。(约 175 字)

评论