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

如果有9个球，其中如果1个球的重量不同，则需要至少2个重量才能找到奇数球。如果有27个球，它需要3次机会。寻找不同重量球所需的最小重量是多少？

9 - > 3 pow 2 - > 2 chances。

27 - > 3 pow 3 - > 3的几率。

问题：什么需要如果给

3 POW 45发现奇数球晕死的最小数目 - 3 POW 40个球

？

不能使用计算器。我认为，需要推导出一些方程/公式。

任何人都可以破解这个难题吗？

来源

2010-11-13 bjskishore123

的密切票是不是因为做重复，而是因为你的问题是题外话，因为它不直接相关的节目。您可能在http://math.stackexchange.com/上有更多的运气。 – 2010-11-13 14:20:39

如果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);

来源

2010-11-13 08:06:03 Violette

嗯，根据3^2 - > 2和3^3 - > 3的第一个假设是真实的，证明我错了。如果是这样，x（N）= log3（N）函数。并且没有必要计算x（a^alpha - b^beta），因为如果beta小于alpha，b^beta = o（a^alpha），所以我们可以放弃它。而且我可以犯一个错误。 – Violette 2010-11-13 08:18:24

要完成：4 =日志（3^4）<日志（3^5-1）<日志（3^5）= 5，从而小区（日志（3^5-1））= 5，所以结果是45 – sdcvvc 2010-11-13 12:00:29

+1：完美。谢谢。也感谢sdcwc。 – bjskishore123 2010-11-13 14:16:39

根据您的例子中，我们可以推断，不同重量的球要么已知较重的或已知较轻。为了简单起见，我认为它更重。

首先让我们来看看为什么在45次称重中可以做到这一点：对于3n个球，可以称n与n，剩下n不称重，并减少到n个球。做40次，减少到一批（3^45-3^40）/ 3^40 = 3^5-1 = 242球。重球在那里。添加一个已知的正常球，所以你有243（3次幂），并继续五次称重，之后你会有重球。

接下来让我们来看看它为什么不能在44个称量或更少来完成：每次称重为您提供了一条信息，这可以被认为是数字0，1，或2 0为“重球在左边“，1为”重球在右边“，2为”重球在未被称量的批次“。无论有多少球与相同数量的球进行称重，情况都是如此。因此，任何44个称量的结果都可以看作是44个数字的序列 - 0,1，和2。有3^44个可能的结果任何策略使用44个称量。但是你有超过3^44个球，所以你不能保证使用只产生3^44个不同答案的实验过程找到合适的球。从信息论的角度来看，“正确答案”中有更多的信息比44次称量所能产生的更多。

来源

2010-11-13 14:12:25 Josephine

当使用秤的传统称重方法时，我们不必推断任何东西，顺便说一句。 – user268396 2010-11-13 14:53:50

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

多少个球最多可以由一个权重进行检查？

答案是3.原因是因为如果你比较三个球中的两个球，你要么立即找到不同重量的球（无论重量还是重量较轻），要么你发现他们的重量是相同的，消除导致第三个球具有不同的重量。

因此，人们可以将N个球分成3个组加上一个M的余数组（其中0 < = M < 3）。每组3个应用一个这样的权重将消除所有球的2/3。这意味着您剩下一组新的球，您需要从中找到不同重量的球，此组中球的数量等于球场（N/3）+ M.

通过应用相同对于这个缩小的球组，您可以在一般情况下在最高限度（log（N）/ log（3））步骤中找到具有不同重量的球。最高限额（）声明的原因是，您最终可能会用完3个组，并留下一组2个球，并且需要额外的1个权重。（如果最后一组只有1个球你不必权衡推断它必须是不同的权重的一个球。更精确地配制成最多地板（日志（N）/日志appearst需要权重的数量（3））+ 1;从那里简单的观察到，如果log（N）/ log（3）是整数，则不需要额外的加权，从而导致更高精度的上限值（log（N）/ log（3））。）

来源

2010-11-13 14:50:03 user268396

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

回答

相关问题