今日学段:组合 + 概率(AMC 10/12 难度)
题目来源:Art of Problems Solving (AoPS) 官方题库 —— 2024 AMC 10 真题
【组合】子集的最大元素个数
难度: ⭐⭐⭐(高中竞赛 · 组合构造与极值)
题目来源: 2024 AMC 10A Problem 20
知识点: 集合构造 · 模运算 · 极值分析
题目:
设集合 $S$ 是 ${1, 2, 3, \dots, 2024}$ 的一个子集,且满足以下两个条件:
- 条件一:$S$ 中任意两个不同元素的差都不能等于 $2$;
- 条件二:$S$ 中任意两个不同元素的差都不能是一个完全平方数。
问 $S$ 中最多可能包含多少个元素?
$\textbf{(A) }436 \qquad \textbf{(B) }506 \qquad \textbf{(C) }608 \qquad \textbf{(D) }654 \qquad \textbf{(E) }675$
解题过程
-
题目要求集合 $S\subseteq{1,2,\dots,2024}$ 满足:任意两元素差不为 $2$、也不为完全平方数,并使 $ S $ 最大。核心思路是「贪心 + 周期性构造」。 - 从小到大枚举可放入 $S$ 的元素。观察规律:合法的 $S$ 起始片段为 \(1,\ 4,\ 8,\ 11,\ 14,\ 18,\ 21,\ 24,\ 28,\ 31,\dots\) 可以看出每 $3$ 个元素构成一个「循环」,且每循环一次整体加 $10$。
- 因此前 $2024$ 个数中,完整循环有 $\lfloor 2024/10\rfloor = 202$ 个,贡献 $202\times 3 = 606$ 个元素。
- 余数为 $4$,在最后的 $2021,2022,2023,2024$ 中还能再放入 $2021$ 与 $2024$ 两个元素,合计 $606+2 = 608$。
- 严谨性:若第一个元素取 $2$,则由归纳可得集合为 ${2,6,10,\dots,2022}$,仅 $506$ 个元素,劣于取 $1$ 的构造,故 $608$ 为最大。
答案: $\boxed{\textbf{(C) } 608}$
常见错误
- 误以为「每 10 个数取 3 个」后余数 4 还能取 3 个(实际只够取 2 个,因为要避开冲突位置)。
- 直接用 $2024\times 0.3$ 估算而忽略边界余数,导致差 1~2。
- 没有验证构造的最优性,把局部贪心当成全局最优。
知识背景
本题属于「极值组合」中的构造型问题:在不相容条件下最大化集合规模。常用手法是寻找周期性规律(模 $m$ 染色),再用带余除法统计完整周期与零散部分。这类问题在 AMC 10/12 中频繁出现,考察观察力与严谨论证。
【概率】白板上的奇数(计数与不变性)
难度: ⭐⭐⭐(高中竞赛 · 组合计数 · 奇偶性不变量)
题目来源: 2024 AMC 10B Problem 16
知识点: 奇偶性 · 不变量 · 操作类组合
题目:
杰瑞喜欢玩数字。有一天,他把 $1$ 到 $2024$ 的所有整数写在白板上。然后他反复进行如下操作:从白板上选出四个数,擦掉它们,并换成它们的和或积(例如,杰瑞第一步可能擦掉 $1,2,3,5$,然后在白板上写下它们的和 $11$ 或积 $30$)。经过反复操作后,杰瑞发现白板上剩下的所有数都是奇数。问此时白板上最多可能有多少个整数?
$\textbf{(A) } 1010 \qquad \textbf{(B) } 1011 \qquad \textbf{(C) } 1012 \qquad \textbf{(D) } 1013 \qquad \textbf{(E) } 1014$
解题过程
- 把 $1$ 到 $2024$ 按奇偶记为 $1,0,1,0,\dots,1,0$。其中奇数有 $1012$ 个,偶数也有 $1012$ 个。
- 目标是让最终白板上所有数都是奇数,即要把 $1012$ 个偶数($0$)全部消掉。每次操作取 $4$ 个数,用它们的和或积替换。
- 关键观察:把四个偶数相加或相乘,结果仍是偶数($0$)。因此可以用 $4$ 个 $0$ 合成 $1$ 个 $0$,把偶数个数从 $1012$ 逐步压缩: \(1012\ \to\ 253\ \to\ 64\ \to\ 16\ \to\ 4\ \to\ 1\) (注意 $253 = 4\times 63 + 1$,合并后剩 $63+1=64$ 个 $0$,依此类推)。
- 最后剩下 $1$ 个 $0$ 时,无法再用 $4$ 个 $0$ 合成,必须消耗 $3$ 个奇数($1$)与之一起操作,得到 $1$ 个奇数,从而偶数归零。
- 每次「合并 $4$ 个 $0$ 成 $1$ 个 $0$」使偶数减 $3$;最后一步使偶数减 $1$ 且奇数减 $3$。总奇数消耗为 $3$,故最终奇数个数为 $1012 - 2 = 1010$。
- 验证:总操作使元素总数每次减 $3$,最终所有数均为奇数,数量为 $\boxed{\textbf{(A) } 1010}$。
答案: $\boxed{\textbf{(A) } 1010}$
常见错误
- 忽略「最后 1 个偶数必须搭 3 个奇数才能消除」,直接算 $1012 - 253 - \dots$ 而漏掉这一步的奇数损耗。
- 误以为乘积一定能产生奇数(四个偶数相乘仍是偶数)。
- 把奇数个数当成单调递减,其实奇数只在最后一步减少。
知识背景
操作类组合题的核心是寻找「不变量」或「单调量」。本题的奇偶性是天然模 2 不变量:四个偶数无论和或积都保持偶数。通过统计偶数被「4 合 1」压缩的次数,即可推出最终奇数数量。这类不变量思想在 AMC/AIME 中极为常见。
本题由 Art of Problems Solving (AoPS) 官方题库抓取,均为 2024 AMC 10 真实考题。
评论