做题了，12个小球，其中一个重量不同，天平称三次能不能找出这个球。

[verdelite]

球外形一样。

做完后可以推广一下（做完后。。。先做12个的）
13个球可以吗？
k个球最多n次可以找出，请描述一般关系式。

[tfusion]

二十几年前就见过这个题

今天仔细想了想才找到答案


分三组，每组4个球。就说1，2，3组吧。

先称1，2组

情况1，两组等重。那重球在第三组。把第三组分成两个球的两组3.1，3.2，称。假设3.1重，从3.1取一个球加上3.2取一个球，再和另外两个称。这样就能知道是哪个球不同了。

情况2，两组不等重。从组1取两个球，组2取两个球合起来和剩下4个球称。这样可以判断哪两个球中有不同的一个。然后把这两个称一下。

13个球3次好像也行。最开始分成4，4，5三个组

[tfusion]

14个球好像3次也行。

[tfusion]

可以写一个递归方程

对n个球，先选2k个两组称，
两组不等重的话，f(n) = f(2k) + 1
等重的话，f(n) = 1 + f(n-2k)

f(n) = min(max(f(2k) + 1, 1 + f(n-2k)))

[tfusion]

上面方程在两组不等重情况下不太对。

[tfusion]

好像应该这样。

递归方程

对n个球，先选2k个两组称，
两组不等重的话，f(n) = 1+log(k)
等重的话，f(n) = 1 + f(n-2k)

f(1) = 0
f(2) = 1
f(n) = 1+ min(max(log(k), f(n-2k))

[nk]

信息论，每一次称重会有三种情况，左边重，右边重，或者一样重。

由于不知到坏是轻的还是重的，不确定的可能性是 2*n.

因此至少需要 ceiling ( log_3(2n) ） 次称重。

然后讨论 在 n=3^(k-1)/2+0.5,3^(k-1)+1.5,...,3^k/2-0.5, 能够找到 k 次的称法把坏球找出来。

[nk]

14个球好像3次也行。

根据我的公式，log_3(2*14) 大于3, 因此至要 4次。

[nk]

如果提前已经知道那个坏球是轻的球，我的那个公式简化成

ceiling ( log_3(n) ） 次称重。

比如27个球，3次就可以了。

[AnonymityFreedom]

如果提前已经知道那个坏球是轻的球，我的那个公式简化成

ceiling ( log_3(n) ） 次称重。

比如27个球，3次就可以了。

同意

[wmwmw]

二十几年前就见过这个题

今天仔细想了想才找到答案


分三组，每组4个球。就说1，2，3组吧。

先称1，2组

情况1，两组等重。那重球在第三组。把第三组分成两个球的两组3.1，3.2，称。假设3.1重，从3.1取一个球加上3.2取一个球，再和另外两个称。这样就能知道是哪个球不同了。，

情况2，两组不等重。从组1取两个球，组2取两个球合起来和剩下4个球称。这样可以判断哪两个球中有不同的一个。然后把这两个称一下。

13个球3次好像也行。最开始分成4，4，5三个组

情况1最后一步只能排除两个球，剩下两个球本来重的重，本来轻的轻，还是不能确定。因为不知道不同的球是重还是轻。

[guaguah]

情况1最后一步只能排除两个球，剩下两个球本来重的重，本来轻的轻，还是不能确定。因为不知道不同的球是重还是轻。

题目上是说12个小球，有一个重量不同。他是理解成了有一个是重球。
不过，情况1是可以解决的。因为第一次两组等重，于是确定了1，2组的8个球都是好的。
从8个好球中取两个和第3组的任意俩个球比较，如等重，第3组剩下的两个球中有一个有问题。否则，用于比较的两个球中有一个有问题。
再在两个可能有问题的球中取一个和一个好球比较。
没有想出来情况2怎么办。

[FGH]

加强版的问题是设计一个称球方案，使得下一步的称法不依赖于之前的结果。

[Bluesky]

20年前做过。很好的题目。如果不靠纸笔，脑子里能想清楚，应该智力在99%人之上。
分三组，每组四个。先称量其中2组，如果平衡，是一条支线，异常球一定在第三组，如果不平衡，命名重球组和轻球组，然后继续。非常考验逻辑能力。

能不靠纸笔把第一支线想清楚的就很了不起了

[rdn123]

对于情况2，知道剩下的4个是好球。

拿3个好球替换随机3个轻的球，用替换的3个轻球替换随机3个重球，3个被替换的重球拿出。

如果天平变平，那么替换的3个重球有一个是重的，再称一次可以找到。

如果天平改变，那么替换的3个轻球有一个是轻的，同样只需再称一遍。

如果天平不变，那么没有被替换的球中可能一个是轻的，或者另一个是重的，只要拿其中一个与其它好球称一次就可以确定了。

[Bluesky]

信息论，每一次称重会有三种情况，左边重，右边重，或者一样重。

由于不知到坏是轻的还是重的，不确定的可能性是 2*n.

因此至少需要 ceiling ( log_3(2n) ） 次称重。

然后讨论 在 n=3^(k-1)/2+0.5,3^(k-1)+1.5,...,3^k/2-0.5, 能够找到 k 次的称法把坏球找出来。

其实就两种，平衡或不平衡。引入左右就浪费称量次数了。你走到天平另外一边看，不平衡其实就是一种情况。

[Bluesky]

二十几年前就见过这个题

今天仔细想了想才找到答案


分三组，每组4个球。就说1，2，3组吧。

先称1，2组

情况1，两组等重。那重球在第三组。把第三组分成两个球的两组3.1，3.2，称。假设3.1重，从3.1取一个球加上3.2取一个球，再和另外两个称。这样就能知道是哪个球不同了。

情况2，两组不等重。从组1取两个球，组2取两个球合起来和剩下4个球称。这样可以判断哪两个球中有不同的一个。然后把这两个称一下。

13个球3次好像也行。最开始分成4，4，5三个组

错了。题目指异常球，并未说轻重。3次称量，不但要找出异常球，还要找出此球是轻于还是重于正常球

[guaguah]

对于情况2，知道剩下的4个是好球。

拿3个好球替换随机3个轻的球，用替换的3个轻球替换随机3个重球，3个被替换的重球拿出。

如果天平变平，那么替换的3个重球有一个是重的，再称一次可以找到。

如果天平改变，那么替换的3个轻球有一个是轻的，同样只需再称一遍。

如果天平不变，那么没有被替换的球中可能一个是轻的，或者另一个是重的，只要拿其中一个与其它好球称一次就可以确定了。

Got it. Thanks.

[nk]

其实就两种，平衡或不平衡。引入左右就浪费称量次数了。你走到天平另外一边看，不平衡其实就是一种情况。

“知道一边的球比另一边的球更重” 获得的信息 比“两边的球重不相等” 要多一些信息的， 是三种情况。

[nk]

错了。题目指异常球，并未说轻重。3次称量，不但要找出异常球，还要找出此球是轻于还是重于正常球

同意前半句，但不同意后半句，题目是要找出异常球就可以了，无须判断“此球是轻于还是重于正常球”。