← Reading List
🧮 奥数题

奥数每日两题 2026-09-28:求 f(2023)(数论函数) / 停车位函数计数

奥数题数学AMC10AMC12数论组合

今日学段:数论 + 组合(AMC 10/12 难度)

题目来源:2023 / 2022 年 AMC 12A 竞赛真题(via AoPS Wiki 镜像仓库,原文来自 artofproblemsolving.com)


【数论】求 $f(2023)$(狄利克雷卷积与积性函数)

难度: ⭐⭐⭐(高中竞赛难度:数论函数与莫比乌斯反演)

题目来源: 2023 AMC 12A Problem 22

知识点: 数论函数 · 狄利克雷卷积 · 积性函数 · 莫比乌斯反演

题目:

设 $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\]

解题过程

思路: 这是一个”约数和”形式的函数方程。我们逐层求出 $f$ 在 $1$、素数、素数幂上的值,再证明 $f$ 是积性函数,最后代入 $2023=7\cdot 17^2$。

第 1 步:$f(1)$ 与素数处的值

  • 当 $n=1$ 时,约数只有 $1$,故 $1\cdot f(1)=1\Rightarrow f(1)=1$。
  • 当 $n=p$ 为素数时,约数为 $1,p$: \(1\cdot f(p)+p\cdot f(1)=1\;\Rightarrow\;f(p)=1-p\)

第 2 步:素数幂 $p^k$ 处的值(归纳)

对 $n=p^k$ 展开: \(f(p^k)+p\,f(p^{k-1})+p^2 f(p^{k-2})+\dots+p^k f(1)=1\) 已知 $f(p^m)=1-p$ 对 $m\le k-1$ 成立(归纳假设),代入后除首项外全部消成 $p$,可得 $f(p^k)=1-p$。 即 对任意素数幂,$f(p^k)=1-p$(与指数 $k$ 无关)。

第 3 步:证明 $f$ 是积性函数

取互异素数 $p,q$,约数为 $1,p,q,pq$: \(f(pq)+p\,f(q)+q\,f(p)+pq\,f(1)=1\) 代入已知值: \(f(pq)+p(1-q)+q(1-p)+pq=1\) \(\Rightarrow\;f(pq)=1-p(1-q)-q(1-p)-pq=(1-p)(1-q)=f(p)\,f(q)\) 所以 $f$ 在互素自变量上满足 $f(ab)=f(a)f(b)$。

第 4 步:计算 $f(2023)$

分解质因数:$2023=7\cdot 17^2$($17^2=289$,$7\cdot 289=2023$)。 由积性: \(f(2023)=f(7)\cdot f(17^2)=(1-7)\cdot(1-17)=(-6)\cdot(-16)=\boxed{96}\)

答案为 (B) 96。

更一般的结论(莫比乌斯反演):实际上 $f(n)=\displaystyle\prod_{p\mid n}(1-p)$,即对每个不同的素因子取 $(1-p)$ 相乘,与上述过程一致。


常见错误

  • 误以为 $f(p^k)$ 随指数 $k$ 变化:其实对所有素数幂恒有 $f(p^k)=1-p$,与 $k$ 无关。
  • 不验证积性就硬算 $2023$ 的全部约数:逐约数展开虽有 $6$ 项也容易算对,但工作量大、易符号出错。
  • 质因数分解错误:把 $2023$ 误拆成 $17\times 119$ 等;正确分解是 $7\times 17^2$。

知识背景

题干中的 $\sum_{d\mid n}d\cdot f(n/d)$ 是数论中的狄利克雷卷积形式 $(\mathrm{id}*f)(n)$。已知卷积结果为常值函数 $1(n)\equiv 1$,由莫比乌斯反演可直接解得 $f(n)=\prod_{p\mid n}(1-p)$。这类”由约数和方程反求函数”的题,是 AMC 12 与 AIME 中常见的数论风格,核心是先把函数在某些特殊点(单位元、素数、素数幂)的取值求出来,再利用积性推广到一般正整数。


【组合】停车函数计数(长度为 5 的字符串)

难度: ⭐⭐⭐(高中竞赛难度:组合计数与停车函数)

题目来源: 2022 AMC 12A Problem 24

知识点: 停车函数 · 组合计数 · 模运算检验

题目:

由数字 $0,1,2,3,4$ 组成的长度为 $5$ 的字符串中,有多少满足:对每一个 $j\in{1,2,3,4}$,字符串中至少有 $j$ 个数字小于 $j$?

(例如 $02214$ 满足条件:小于 $1$ 的数字至少 $1$ 个、小于 $2$ 的至少 $2$ 个、小于 $3$ 的至少 $3$ 个、小于 $4$ 的至少 $4$ 个;$23404$ 不满足,因为它没有至少 $2$ 个数字小于 $2$。)

\[\textbf{(A) }500\qquad\textbf{(B) }625\qquad\textbf{(C) }1089\qquad\textbf{(D) }1199\qquad\textbf{(E) }1296\]

解题过程

思路一(停车函数,优雅解法):

经典结论:由数字 $0,1,\dots,n-1$ 组成的长度为 $n$ 的字符串,满足”对每个 $k=1,\dots,n$,至少有 $k$ 个数字小于 $k$”的,恰好一一对应于停车函数(parking functions),其总数为 $(n+1)^{n-1}$。

直观模型:有 $n+1$ 个环形车位,第 $i$ 辆车想停在第 $c_i$ 位,被占则顺延到下一个空位;最终恰剩一个空位。满足上述”至少 $k$ 个小于 $k$”条件的字符串,恰好是让”车位 $n$”成为那个空位的停车函数。由于把每个 $c_i$ 都加 $1$(模 $n+1$)会循环平移空位,每种字符串恰有唯一偏移使空位落在 $n$,因此合法字符串数为总函数数 $(n+1)^n$ 除以 $(n+1)$,即 $(n+1)^{n-1}$。

代入 $n=5$: \((5+1)^{5-1}=6^4=1296\)

所以答案是 (E) 1296。

思路二(模 5”奶酪”检验,用于快速核对):

考虑满足条件的字符串计数 $N$。对任一合法字符串统计各数字出现次数 $a,b,c,d,e$(对应 $0\sim 4$),则排列数为 $\frac{5!}{a!b!c!d!e!}$,它总是 $5$ 的倍数,除非某个字母出现 $5$ 次(其余为 $0$)。唯一单数字字符串是 $00000$,它合法。故 $N\equiv 1\pmod 5$。选项中只有 $1296\equiv 1\pmod 5$,故选 (E)。


常见错误

  • 把条件读反:误以为”至少有 $j$ 个数字大于等于 $j$”,导致方向完全相反。
  • 只用总数 $5^5=3125$:忘记题目对每一位 $j$ 都有约束,绝大多数字符串并不合法。
  • 忽略”必须出现 $0$”:当 $j=1$ 时要求至少 $1$ 个数字小于 $1$,即必须含 $0$;但错误地额外强加其他不存在的限制。

知识背景

停车函数(Parking Functions)是组合数学的经典对象:设 $n$ 辆车依次驶入 $n$ 个(或 $n+1$ 个环形)车位,每辆车有偏好车位 $c_i$,被占则顺延至下一个空位。若存在一种停法使所有车都停入,则序列 $(c_1,\dots,c_n)$ 称为停车函数。其总数恰为 $(n+1)^{n-1}$,与本题的计数条件等价。该结构还联系到树计数(Cayley 公式)、修辞森林等,是竞赛与大学组合中反复出现的高频模型。

评论