一道称药片的微策略智力题

gxqcn

有1到10，10个盒子，每个盒子里面装了500个药片，药片的规格有9g或者10g的，每个盒子装的药片规格都是一样的。
给你一个秤（能够秤出质量），如何能够只秤一次，就找到1到10盒子里的药片规格？（知道哪些盒子装的是9g的，哪些装的是10g的？）

注：这是浏览CSDN看到的，感觉比较有趣，大家一道讨论下（原帖：http://bbs.csdn.net/topics/390629023，请先别急着点击）。

knate

由于每种药规格只有两个规格,而且两者误差为1,因此直接可以看成0,1两种,
原题可以看成
∑▒〖a_i X_i 〗=M ,a_i=0,1
唯一性非负整数表示问题.
最简单的一个解,应该是,该求和是一个按权展开式,权最小的为2,因此最大值大致在512,原则上超出500,但是思路应该是对的.

如果是该称是天平的话,看成是
∑&#9618;〖a_i X_i 〗=M ,a_i=0,1,-1,这个三进制展开的话,那么3^(10 / 2) < 500,应该是合适的.

如果只能放一边
∑&#9618;〖a_i X_i 〗=M ,a_i=0,1,2,这个三进制展开的话,那么2 * 3^(10 / 2) < 500,似乎应该也是合适的.


补充内容 (2013-12-6 11:27):
0,1,2这个三进制似乎有问题

补充内容 (2013-12-6 12:08):
-1,0,1,这个三进制有时可以取消天平限制,这题 一般的称也是可以的..    不可以修改贴,郁闷

补充内容 (2013-12-6 12:14):
可以无视我的了,,,,,,,我发现反例了.

蓉依山爸

这题简单：

1号瓶拿2的0次方（1）粒药，2号瓶拿2的1次方（2）粒药，3号瓶拿2的2次方（4）粒药，4号瓶拿2的3次方（8）粒药……10号瓶拿2的9次方（512）粒药

称重后，看超出90g多少？再把超出部分的重量转化为2进制，就知道是哪些瓶子里面的药，是10g一片了。最后，剩下的瓶子，装的都是9g一片的药

wayne

能把药片物理性的掐成一半吗，

===
也许掐不太准确， 用小刀 穿过 药片的中心，轻轻的摁着，切一刀吧。

wayne

前面我们的思路 都是 把二的幂 当作 每个盒子所取的药片的个数 的权重。

可不可以是其他的数字，比如500以内的 某10个素数？

我觉得是大有可能的，  无非就是解一个 不定方程的 正整数解。

wayne

每种药片要么是9g，要么是10g，总共排列数是 2^10 = 1024.
1024 好小啊。 写一个程序，brute force！
随机的选择 10个比较靠近的大整数，分别计算所有排列对应的可能重量。 如果重量值 都不重复，那么就是可行的方案

gxqcn

实际上，可以把药片的质量看作：0克 or 1克，
并不会对结果产生影响，但可以简化思路。

如果有更多不同的质量数，则按如下过程简化：
1、各数除以它们的最大公约数；
2、各数减去它们之间的最小值。

wayne

gxqcn 发表于 2013-12-6 15:52
实际上，可以把药片的质量看作：0克 or 1克，
并不会对结果产生影响，但可以简化思路。

有这两个原则的话，二进制的表达应该就是最紧凑的组合了，于是，500以内就没有答案了。

wayne

gxqcn 发表于 2013-12-6 15:52
实际上，可以把药片的质量看作：0克 or 1克，
并不会对结果产生影响，但可以简化思路。

看成0g，1g 就不能根据 各数减去它们之间的最小值 来简化了
所以该题 答案还是open的

gxqcn

说一下我之前给出简化两原则的思路：

假设我们已经给出了一种可行方案，分别取各盒药片若干粒放置天平左盘，右盘放置一定的砝码使之平衡。
我们可以仅根据砝码读数，以及我们选择的加权系数，判定出唯一的单粒质量组合序列。

好了，我们假想现在的每粒药片实际上均可k等分，那么我们仅取各自的k分之一，则对应的砝码读数也缩减为先前的1/k，
我们依然可以仅根据砝码读数，以及我们选择的加权系数，判定出先前的唯一的单粒质量组合序列。

接下来，咱们再对每粒药片减少b克，右边的砝码对应地减少（b*药片称量总数）而使天平再次平衡，
我们仍然可以仅根据砝码读数，以及我们选择的加权系数，判定出先前的唯一的单粒质量组合序列。

因为我们上述过程都是相当于对一个线性不定方程作线性变换，不会影响方程的解。
但是简化后，有利于简化思路（对于人脑来说可减轻点计算和记忆负担；对于电脑来说也许效果甚微）。