← Reading List
🧮 奥数题

奥数每日两题 2026-09-10:进制整除计数 / 3×3网格猜格

奥数题数学AMC10AMC12数论组合

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

题目来源:2024 AMC 12A Problem 11、2023 AMC 12B Problem 5(真实竞赛真题,来源于 AoPS 公开题库归档 songsjun/AMC12_Problems)


【数论】进制表示下的整除计数

难度: ⭐⭐⭐(高中竞赛难度 · 同余分类讨论)

题目来源: 2024 AMC 12A Problem 11

知识点: 进制展开 · 同余(模 8 / 模 16)· 奇偶性分类 · 等差数列计数

题目:

在 $5 \le b \le 2024$ 范围内,恰好有 $K$ 个正整数 $b$,使得 $b$ 进制下的整数 $2024_b$ 能被 $16$(十进制)整除。问 $K$ 的各位数字之和是多少?

\[\textbf{(A) }16\qquad\textbf{(B) }17\qquad\textbf{(C) }18\qquad\textbf{(D) }20\qquad\textbf{(E) }21\]

解题过程

把 $2024_b$ 按 $b$ 进制展开:

\[2024_b = 2\cdot b^3 + 0\cdot b^2 + 2\cdot b + 4 = 2b^3 + 2b + 4\]

要求它被 $16$ 整除,即

\[2b^3 + 2b + 4 \equiv 0 \pmod{16}\]

两边同除以 $2$(注意 $2$ 与 $16$ 不互素,但这里等价于模 $8$ 的同余):

\[b^3 + b + 2 \equiv 0 \pmod{8}\]

按 $b$ 的奇偶性分类讨论。

情况一:$b$ 为偶数。 设 $b = 2a$,代入:

\[(2a)^3 + 2a + 2 = 8a^3 + 2a + 2 \equiv 2a + 2 \pmod{8}\]

要求 $2a + 2 \equiv 0 \pmod{8}$,即 $a + 1 \equiv 0 \pmod{4}$,所以 $a \equiv 3 \pmod{4}$。

于是 $b = 2(4x+3) = 8x + 6$,即 $b \equiv 6 \pmod{8}$。

情况二:$b$ 为奇数。 设 $b = 2a+1$,代入:

\[(2a+1)^3 + (2a+1) + 2 = 8a^3 + 12a^2 + 6a + 1 + 2a + 1 + 2 = 8a^3 + 12a^2 + 8a + 4\]

模 $8$ 下只需看 $4a^2 + 4$:

\[4a^2 + 4 \equiv 0 \pmod{8} \;\Longrightarrow\; a^2 \equiv 1 \pmod{2}\]

即 $a$ 为奇数。于是 $b = 2(2x+1) + 1 = 4x + 3$,即 $b \equiv 3 \pmod{4}$。

注意:两种情况奇偶互斥,没有重叠,可以安全相加计数。

计数: 在 $5 \le b \le 2024$ 中:

  • $b \equiv 6 \pmod{8}$:$6, 14, 22, \dots, 2022$。共 $\frac{2022-6}{8}+1 = 253$ 个。
  • $b \equiv 3 \pmod{4}$:在此区间中为 $7, 11, 15, \dots, 2023$(注意 $b=3$ 不满足 $b\ge 5$,已排除)。共 $\frac{2023-7}{4}+1 = 505$ 个。

合计 $K = 253 + 505 = 758$,各位数字之和 $7+5+8 = \boxed{20}$,对应选项 (D)。


常见错误

  • 错误1: 直接对 $2b^3+2b+4 \equiv 0 \pmod{16}$ 做因式分解,忽略了系数 $2$ 与模 $16$ 不互素,不能直接约去;正确做法是先化为模 $8$ 的同余 $b^3+b+2\equiv 0\pmod 8$。
  • 错误2: 数偶数类时把 $b=6$ 这一项漏算或把 $2024$ 误当作上界项;应检查 $2022 = 8\times252 + 6$ 确实是末项。
  • 错误3: 忘记排除 $b=3$(不满足 $b\ge 5$),导致多算 $1$ 个得到 $759$,再把 $759$ 各位和算成 $21$ 错选 (E)。

知识背景

进制展开把“不同进位制下的数”统一成关于基数 $b$ 的多项式,是研究整除性的基本工具。本题核心技巧是“模 $8$ / 模 $16$ 下的奇偶分类”——当多项式含奇偶交替项时,按 $b$ 的奇偶性拆开常能把高次项消成低次同余,从而化为简单的线性同余方程。这类“先降次、再分类、最后等差数列计数”的思路,在 AMC 10/12 与 AIME 的数论题中非常常见。


【组合】3×3 网格里的最优猜格策略

难度: ⭐⭐⭐(高中竞赛难度 · 组合最优化/博弈策略)

题目来源: 2023 AMC 12B Problem 5

知识点: 染色论证(棋盘染色)· 命中集(hitting set)· 奇偶分类策略

题目:

你正在玩一个游戏:在一个 $3\times 3$ 的方格中,有一个 $2\times 1$ 的矩形(骨牌)盖住了两个相邻的方格(横放或竖放均可),但你不被告知它盖住了哪两个格。你的目标是至少找到被这个矩形盖住的一个方格。每一“轮”你可以猜一个方格,随后会被告知该方格是否被隐藏的矩形盖住。为了保证你猜中的方格中至少有一个确实被矩形盖住,你最少需要几轮?

\[\textbf{(A) }3\qquad\textbf{(B) }5\qquad\textbf{(C) }4\qquad\textbf{(D) }8\qquad\textbf{(E) }6\]

解题过程

上界(构造一种 4 轮必胜策略):棋盘染色法。

把 $3\times 3$ 网格像国际象棋棋盘一样黑白交替染色,令左上角为白格,则白格有 $5$ 个、黑格有 $4$ 个:

白 黑 白
黑 白 黑
白 黑 白

关键点:任何一个 $2\times 1$ 骨牌都恰好盖住一个白格和一个黑格(相邻两格必然异色)。

因此,只要我们把所有 $4$ 个黑格全部猜一遍,无论隐藏的骨牌在哪里,它都一定盖住了某个黑格,从而在 4 轮内必定命中。所以所需轮数 $\le 4$。

下界(证明 3 轮不够):

$3\times 3$ 网格中共有 $12$ 种可能的骨牌位置(横放 $3\times 2 = 6$ 种,竖放 $2\times 3 = 6$ 种)。每个方格最多被 $4$ 个骨牌覆盖(中间的格子被 4 个覆盖,边中格被 3 个,角格被 2 个)。

若只猜 $3$ 个方格,即使最理想地选覆盖数最多的格子,最多也只能排除 $3\times 4 = 12$ 个位置;但中心格被 4 个骨牌覆盖、其余 8 格各被至多 2 个“未被中心格覆盖”的骨牌覆盖,若要 3 轮覆盖全部 12 个骨牌,需 $1 + \frac{12-4}{2} = 5$ 轮,矛盾——所以不猜中心格时无法用 3 轮覆盖所有骨牌。而猜中心格的方案本身也至少需要 5 轮。综上 3 轮无法保证命中。

综合上下界,最少需要 $\boxed{4}$ 轮,对应选项 (C)。

(更直观的记忆:染色后较小的那一类颜色只有 4 格,且每根骨牌必跨一黑一白,所以“猜完少数色”就是最优策略。)


常见错误

  • 错误1: 以为每轮能排除相邻格,从而认为猜 8 个角/边就能覆盖;题目求的是“保证命中”的最少轮数,而不是最坏情况乱猜。
  • 错误2: 忽略“骨牌必跨异色格”这一染色不变量,转而用纯枚举,容易漏掉某种骨牌位置而误判 3 轮可行。
  • 错误3: 把 $3\times3$ 误当成更大网格,或把黑格数数错成 5(白格才是 5 个),导致上下界算反。

知识背景

棋盘染色(奇偶染色)是组合数学里最经典、也最 powerful 的“不变量”论证之一。它的精髓在于:把全局结构用一种简单的二分类标记,使得某个操作(本题中的骨牌覆盖)必然满足某种跨类性质,从而把“存在性/最优化”问题转化为“两类各有多少个”的计数问题。从多米诺骨牌铺砖(是否能用骨牌铺满缺角的棋盘)到国际象棋马步遍历,染色论证无处不在,是 AMC/AIME/USACO 组合题的必备武器。


两题均取自真实 AMC 12 竞赛真题(2024 AMC 12A #11、2023 AMC 12B #5),由公开题库归档整理,题目与标准答案均与原卷一致。

评论