Cards from Their Sum


Table of Contents

题目

魔术师洗了洗牌,然后从牌堆顶上发了\(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\}.\]

Next