问找到不同重量的球所需的最小重量是多少？

EN

若3^x = N球和x -- number of weighs，x = log3(N)；

3^x = 3^45 - 3^40;
3^x = 3^40 * (3^5 - 1);
x = log3(3^40) + log3(3^5 - 1) = 40 + log3(242);
real_x = ceil(x);

得到答案的另一种直观方法是问自己这个问题：

一个重量最多可以检查多少个球？

答案是3，因为如果你比较三个球中的两个，你要么立即找到一个不同重量的球(不管是重的还是轻的)，要么你发现它们的重量是相等的，在消除过程中导致第三个球的重量不同。

因此，我们可以将N个球除以3的群，再加上一个M的剩余组(用0<=M<3)。每组3人使用一次这样的加权将消除所有球的2/3 3rds。这意味着你剩下一组新的球，你需要从中找到一个有不同重量的球，这个组的球数等于地板(N/3)+ M。

通过将同样的步骤应用于这组减少的球，您可以在最多的天花板(log(N)/log(3))步骤中找到一般情况下不同重量的球。使用reason ()语句的原因是，您最终可能会用完3组，并留下一组由2个球组成的组，需要增加1个权重。(如果最后一组只有一个球，你不必称它的重量来推断它一定是一个不同重量的球。更精确地表述了最高层( log(N)/log(3) +1)所需的加权数；由此可以简单地观察到，如果log(N)/log(3)是整数，则不需要增加1次加权，就可以得到更精确的上限值(log(N)/log(3))。

根据你的例子，我们必须推断出不同重量的球要么更重，要么更轻。为了简单起见，我假设它更重。

首先，让我们来看看为什么在45次称重中可以做到这一点:对于3n个球，我们可以称n对n，不需要称n，然后将n减为n。这样做40次，减少到一批(3^45-3^40)/3^40 = 3^5-1 =242个球。重球就在里面的某个地方。添加一个已知的普通球，所以你有243 (再次3的力量)，并继续五重，然后你将有沉重的球。

接下来，让我们看看为什么不能在44种或更少的称量中完成:每次称重都会提供一条信息，这些信息可以被认为是“重球在左边”、“重球在右边”和“重球在未称重的批次中”的数字0、1或2.0。不管有多少个球与同样数量的球称重，这都是真的。因此，任何44次加权的结果都可以看作是44位数的序列-0‘，1’和2's，使用44次加权的任何策略都有3^44种可能的结果。但是你有超过3^44个球，所以你不能保证用一个只产生3^44个不同答案的实验过程来找到正确的球。从信息论的角度看，“正确答案”中的信息比44次称重所能产生的信息更多。