今日学段:数论 + 组合(AMC 10/12 难度)
题目来源:2023 年 AMC 10 竞赛真题(来源 AoPS Wiki,经 kaggle-aimo/amc_filtered 公开题库核验)
【数论】平方数整除计数
难度: ⭐⭐⭐(高中竞赛入门难度,整除与完全平方数基础)
题目来源: 2023 AMC 10A Problem 3
知识点: 完全平方数性质 · 整除判定 · 不等式估算
题目:
有多少个小于 $2023$ 的正整数完全平方数能被 $5$ 整除?
解题过程
- 若完全平方数 $N = m^2$ 能被 $5$ 整除,由素数整除性质可知 $5 \mid m$,即 $m$ 必为 $5$ 的倍数,设 $m = 5k$($k$ 为正整数)。
- 于是 $N = (5k)^2 = 25k^2$。要求 $25k^2 < 2023$。
- 两边除以 $25$:$k^2 < \dfrac{2023}{25} = 80.92$。
- 因为 $k$ 为正整数,满足 $k^2 \le 80$ 的最大 $k$ 为 $8$(注意 $9^2 = 81 > 80$)。
- 故 $k = 1, 2, \dots, 8$,共 $\boxed{8}$ 个。
常见错误
- 把 $k = 0$ 算进去($0$ 不是正整数,且 $0^2 = 0$ 不算”正”完全平方数)。
- 误算成 $9$ 个(忘记 $25 \times 81 = 2025 > 2023$,应严格不等式)。
- 忘记”被 $5$ 整除的完全平方数其平方根必被 $5$ 整除”,从而枚举所有平方数逐个判断,既慢又易漏。
知识背景
完全平方数被素数整除的性质:若素数 $p \mid m^2$,则 $p \mid m$。这是欧几里得引理的直接推论,也是数论中最常用的工具之一。推广到一般整数:若 $m^2$ 被 $p$ 整除,则 $m$ 必被 $p$ 整除;若 $m^2$ 被 $p^2$ 整除,则 $m$ 被 $p$ 整除。这类”整除传递到平方根”的直觉,在约数计数、质因数分解题中反复出现。
【组合】网格骨牌覆盖
难度: ⭐⭐⭐⭐(高中竞赛中等难度,集合覆盖与对偶思想)
题目来源: 2023 AMC 10B Problem 10
知识点: 独立集 · 顶点覆盖 · 最坏情形保证策略
题目:
你正在玩一个游戏。一个 $2 \times 1$ 的矩形(骨牌)恰好覆盖 $3 \times 3$ 方格网格中的两个相邻方格(可横放或竖放),但你不知道它覆盖的是哪两格。你的目标是在若干回合后,至少猜中一个被骨牌覆盖的方格。每”回合”你猜一格,系统告诉你该格是否被隐藏的骨牌覆盖。要保证无论骨牌放在哪里,你都能猜中至少一个被覆盖的方格,最少需要几回合?
解题过程
- 把问题转化为集合覆盖:在 $9$ 格中选出最少的格子集合 $S$,使得每一种可能的骨牌摆放都至少覆盖 $S$ 中的一格。
- 反向思考:设 $T$ 为”未被猜”的格子集合。如果存在某种骨牌完全落在 $T$ 内,那么你会全部猜错。要避免这种情况,必须保证 $T$ 中不含任何相邻的两格——即 $T$ 是一个独立集(independent set)。
- 对 $3 \times 3$ 棋盘做国际象棋染色(黑白相间),一种颜色有 $5$ 格,另一种颜色有 $4$ 格;同色格互不相邻,所以最大独立集大小为 $5$。
-
因此 $ T \le 5$,从而必须猜的格子数 $ S = 9 - T \ge 9 - 5 = 4$。 - 构造可行性:猜同色的 $4$ 格(或任意能”击中”全部 $12$ 种骨牌摆放的 $4$ 格),即可保证命中。例如去掉一个角及其对角,剩下的 $4$ 格能覆盖所有骨牌位置。
- 综上最少需要 $\boxed{4}$ 回合。
常见错误
- 用”平均/概率”思路作答(本题要求的是最坏情形下的保证,不是期望回合数)。
- 认为 $3$ 回合足够——实际上可构造出一种骨牌摆放,使任意指定的 $3$ 格都落空。
- 漏数骨牌摆放总数(横放 $6$ 种 + 竖放 $6$ 种 = $12$ 种),导致构造验证不全。
知识背景
本题对应组合优化中的顶点覆盖(Vertex Cover)与独立集(Independent Set)对偶:在一个图中,最小顶点覆盖大小 = 顶点数 − 最大独立集大小。骨牌摆放构成”边”,方格是”顶点”,我们要覆盖所有边。虽然一般图上的最小顶点覆盖是 NP 难问题,但在网格这类小结构上可用染色法直接求得。这类”最坏保证 + 对偶转化”思想,也在博弈论和信息论的最小查询策略中常见。
每日两题由真实 AMC 10/12 竞赛题库抓取整理,题目版权归 MAA / AoPS 所有。
评论