题目
魔术师洗了洗牌,然后从牌堆顶上发了\(5\)张牌,背面朝上放到你摊开的手里。
她让你秘密地任选其中若干张,只把这些牌点数之和告诉她(\(J\)算\(11\),\(Q\)算\(12\),\(K\)算\(13\))。
你照做以后,魔术师竟然准确说出了你选的是哪几张牌,连花色都说对了。
后来你发现她的洗牌其实有问题:最上面的\(5\)张牌根本没有被打乱,所以这\(5\)张牌本来就是她事先挑好的,花色她当然也早已记住。真正需要精心挑选的,是这\(5\)张牌的点数:她必须保证你无论选其中哪几张,只要知道总和,就能唯一反推出你选了哪些点数。
所以,如果你也想表演这个魔术,就需要找出\(5\)个互不相同、介于\(1\)到\(13\)之间的整数,使得它们的每一个子集都有不同的元素和。
你能做到吗?
分析
可以,用构造法来做。
一个直觉是:牌点越大越好。从\(K=13\)开始,每一步都尽量选还没用过的最大点数,只要它不会造成“两个不同选法得到同一个总和”。
先把过程整理成表格:
| 步骤 | 尝试的点数 | 结论 | 原因 |
|---|---|---|---|
| 1 | 13 | 选 | 起点(\(K\)) |
| 2 | 12 | 选 | 暂无冲突 |
| 3 | 11 | 选 | 暂无冲突 |
| 4 | 10 | 不选 | \(10+13=11+12\),出现同和冲突 |
| 5 | 9 | 选 | 无冲突 |
| 6 | 8 | 不选 | \(8+13=9+12\),出现同和冲突 |
| 7 | 7 | 不选 | \(7+13=9+11\),出现同和冲突 |
| 8 | 6 | 选 | 无冲突 |
于是贪心构造得到
\[ \boxed{6,9,11,12,13}。\]
因此,这\(5\)张牌的任意子集总和都不会重复,题目要求满足。
另外,第四步也可以走另一条分支:在\(10\)不行之后,不选\(9\)而改选\(6\),再继续按同样规则选第五张,可得到第二组。
| 分支步骤 | 尝试的点数 | 结论 | 原因 |
|---|---|---|---|
| A1 | 13,12,11 | 先选 | 与主流程相同 |
| A2 | 10 | 不选 | \(10+13=11+12\) |
| A3 | 6 | 选 | 无冲突 |
| A4 | 3 | 选 | 无冲突 |
得到
\[ \boxed{3,6,11,12,13}。\]
于是可以得到两组可行解(忽略顺序):
\[ \{6,9,11,12,13\},\ \{3,6,11,12,13\}.\]