钥匙、锁、盒子、礼物的装箱问题

[geelaw]

题目来自 SPARC 的申请。

有一个卖锁的，1 块钱可以买 2 把相同的钥匙 a, b 和 2 把相同的（打开的）锁头 A, B，这就是说 a 可以开 A、B 中的任意一个，b 也可以开 A、B 中的任意一个。但是这个钥匙是 一次性 的——一旦用来打开一把锁头，钥匙就会永远插在里面拔不出来（即使再把锁头锁上也不能）。此外，每次购买得到的钥匙 /锁对儿都是不同的，不能互相开。

你有无限量供应的各种大小的盒子（可以放任何东西，包括钥匙，甚至盒子本身），都是免费的。盒子可以用一把锁锁住，如果被锁住，就只有用对应的一把钥匙才能得到盒子里面的东西（代价自然是牺牲一把钥匙）。

现在有 100 个礼物要送给朋友，你要购买一些钥匙 /锁，使用一些盒子，巧妙地包装这些东西；完成之后，你把所有的盒子都给朋友，并且把 一部分钥匙 给朋友；你的目的是让朋友能选择任何 50 个他想要的礼物，但是不能拿到 51 个礼物。要做到这点，你需要花多 少 钱？

如果题目本身比较拗口，考虑 2 选 1 的情况：用两个盒子，分别放礼物 1 和礼物 2，然后用两把相同的锁分别锁上，最后交给朋友 1 把能开那个锁的钥匙。此时朋友能且只能选择开两个盒子里的一个，因此能拿到 2 个里面的任意 1 个，但不能拿到 2 个。

再复杂一点的例子是 6 选 3，下图是一个可能的方案（数字代表物品，方框代表盒子，盒子的颜色和钥匙的颜色对应锁的颜色，在盒子外面的钥匙提供给朋友）。

这个题目似乎并不是很平凡，大家可以开动脑筋。

你可以查看 这篇博文 了解我和我的同学目前知道的内容，以及我们讨论中的一些小幽默。