专题地图 › 排列组合
2015 年山西预赛 · 第 1 题
F2填空题排列组合
设 M={1,2,…,12},三元集 A={a,b,c} 满足 A⊂M,且 a+b+c 为平方数,则这种集合 A 的个数是。
作答
分数写 a/b,根号写 √ 或 sqrt,π 写 pi 也可以。
标准答案:26
解析
思路
集合无序,先固定严格递增表示,再按和的平方值及最小元素分层。
解答
将每个三元集唯一写为 1≤a<b<c≤12。其和在六到三十三之间,只可能为平方数 9,16,25。固定和 s 与最小数 a 后,c=s−a−b,合法 b 满足
max(a+1,s−a−12)≤b≤min(11,⌊2s−a−1⌋).
依此逐层计数如下,空区间计零:
a1234567s=92100000s=165431000s=250112231
a≥8 时最小和已超过二十五,无须再计。故总数为 3+13+10=26。
复核
例如和为九的三个集合为 {1,2,6},{1,3,5},{2,3,4};和为25且 a=6 时为 {6,7,12},{6,8,11},{6,9,10}。表中按唯一最小元素分类,不乘排列因子。
方法总结
数三元集先排序消除无序性,再固定总和与最小参数,用中间元素的完整整数区间计数。
为什么评为 F2(会透露解法方向)
须先将无序三元集标准化,再列尽可行平方和并按最小元素精确计算整数区间,防止重复和漏边界。
用到的方法(会透露解法方向)
核心工具:有限枚举与去重
专题卡:选唯一参数表示,再按范围分层计数