分页： 1 / 2
#1 做题了，12个小球，其中一个重量不同，天平称三次能不能找出这个球。
发表于 ： 2024年 4月 27日 16:02
由 verdelite
球外形一样。
做完后可以推广一下（做完后。。。先做12个的）
13个球可以吗？
k个球最多n次可以找出，请描述一般关系式。
#2 Re: 做题了，12个小球，其中一个重量不同，天平称三次能不能找出这个球。
发表于 ： 2024年 4月 27日 16:59
由 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三个组
#3 Re: 做题了，12个小球，其中一个重量不同，天平称三次能不能找出这个球。
发表于 ： 2024年 4月 27日 17:01
由 tfusion
14个球好像3次也行。
#4 Re: 做题了，12个小球，其中一个重量不同，天平称三次能不能找出这个球。
发表于 ： 2024年 4月 27日 17:11
由 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)))
#5 Re: 做题了，12个小球，其中一个重量不同，天平称三次能不能找出这个球。
发表于 ： 2024年 4月 27日 17:22
由 tfusion
上面方程在两组不等重情况下不太对。
#6 Re: 做题了，12个小球，其中一个重量不同，天平称三次能不能找出这个球。
发表于 ： 2024年 4月 27日 17:25
由 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))
#7 Re: 做题了，12个小球，其中一个重量不同，天平称三次能不能找出这个球。
发表于 ： 2024年 4月 28日 08:15
由 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 次的称法把坏球找出来。
#8 Re: 做题了，12个小球，其中一个重量不同，天平称三次能不能找出这个球。
发表于 ： 2024年 4月 28日 08:17
由 nk
tfusion 写了： 2024年 4月 27日 17:01
14个球好像3次也行。
根据我的公式，log_3(2*14) 大于3, 因此至要 4次。
#9 Re: 做题了，12个小球，其中一个重量不同，天平称三次能不能找出这个球。
发表于 ： 2024年 4月 28日 08:19
由 nk
如果提前已经知道那个坏球是轻的球，我的那个公式简化成
ceiling ( log_3(n) ） 次称重。
比如27个球，3次就可以了。
#10 Re: 做题了，12个小球，其中一个重量不同，天平称三次能不能找出这个球。
发表于 ： 2024年 4月 28日 09:55
由 AnonymityFreedom
nk 写了： 2024年 4月 28日 08:19
如果提前已经知道那个坏球是轻的球，我的那个公式简化成
ceiling ( log_3(n) ） 次称重。
比如27个球，3次就可以了。
同意
#11 Re: 做题了，12个小球，其中一个重量不同，天平称三次能不能找出这个球。
发表于 ： 2024年 4月 28日 10:57
由 wmwmw
tfusion 写了： 2024年 4月 27日 16:59
二十几年前就见过这个题
今天仔细想了想才找到答案
分三组，每组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最后一步只能排除两个球，剩下两个球本来重的重，本来轻的轻，还是不能确定。因为不知道不同的球是重还是轻。
#12 Re: 做题了，12个小球，其中一个重量不同，天平称三次能不能找出这个球。
发表于 ： 2024年 4月 28日 11:26
由 guaguah
wmwmw 写了： 2024年 4月 28日 10:57
情况1最后一步只能排除两个球，剩下两个球本来重的重，本来轻的轻，还是不能确定。因为不知道不同的球是重还是轻。
题目上是说12个小球，有一个重量不同。他是理解成了有一个是重球。
不过，情况1是可以解决的。因为第一次两组等重，于是确定了1，2组的8个球都是好的。
从8个好球中取两个和第3组的任意俩个球比较，如等重，第3组剩下的两个球中有一个有问题。否则，用于比较的两个球中有一个有问题。
再在两个可能有问题的球中取一个和一个好球比较。
没有想出来情况2怎么办。
#13 Re: 做题了，12个小球，其中一个重量不同，天平称三次能不能找出这个球。
发表于 ： 2024年 4月 28日 11:30
由 FGH
加强版的问题是设计一个称球方案，使得下一步的称法不依赖于之前的结果。
#14 Re: 做题了，12个小球，其中一个重量不同，天平称三次能不能找出这个球。
发表于 ： 2024年 4月 28日 11:35
由 Bluesky
20年前做过。很好的题目。如果不靠纸笔，脑子里能想清楚，应该智力在99%人之上。
分三组，每组四个。先称量其中2组，如果平衡，是一条支线，异常球一定在第三组，如果不平衡，命名重球组和轻球组，然后继续。非常考验逻辑能力。
能不靠纸笔把第一支线想清楚的就很了不起了
#15 Re: 做题了，12个小球，其中一个重量不同，天平称三次能不能找出这个球。
发表于 ： 2024年 4月 28日 11:44
由 rdn123
对于情况2，知道剩下的4个是好球。
拿3个好球替换随机3个轻的球，用替换的3个轻球替换随机3个重球，3个被替换的重球拿出。
如果天平变平，那么替换的3个重球有一个是重的，再称一次可以找到。
如果天平改变，那么替换的3个轻球有一个是轻的，同样只需再称一遍。
如果天平不变，那么没有被替换的球中可能一个是轻的，或者另一个是重的，只要拿其中一个与其它好球称一次就可以确定了。
#16 Re: 做题了，12个小球，其中一个重量不同，天平称三次能不能找出这个球。
发表于 ： 2024年 4月 28日 11:54
由 Bluesky
nk 写了： 2024年 4月 28日 08:15
信息论，每一次称重会有三种情况，左边重，右边重，或者一样重。
由于不知到坏是轻的还是重的，不确定的可能性是 2*n.
因此至少需要 ceiling ( log_3(2n) ） 次称重。
然后讨论 在 n=3^(k-1)/2+0.5,3^(k-1)+1.5,...,3^k/2-0.5, 能够找到 k 次的称法把坏球找出来。
其实就两种，平衡或不平衡。引入左右就浪费称量次数了。你走到天平另外一边看，不平衡其实就是一种情况。
#17 Re: 做题了，12个小球，其中一个重量不同，天平称三次能不能找出这个球。
发表于 ： 2024年 4月 28日 11:57
由 Bluesky
tfusion 写了： 2024年 4月 27日 16:59
二十几年前就见过这个题
今天仔细想了想才找到答案
分三组，每组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次称量，不但要找出异常球，还要找出此球是轻于还是重于正常球
#18 Re: 做题了，12个小球，其中一个重量不同，天平称三次能不能找出这个球。
发表于 ： 2024年 4月 28日 12:14
由 guaguah
rdn123 写了： 2024年 4月 28日 11:44
对于情况2，知道剩下的4个是好球。
拿3个好球替换随机3个轻的球，用替换的3个轻球替换随机3个重球，3个被替换的重球拿出。
如果天平变平，那么替换的3个重球有一个是重的，再称一次可以找到。
如果天平改变，那么替换的3个轻球有一个是轻的，同样只需再称一遍。
如果天平不变，那么没有被替换的球中可能一个是轻的，或者另一个是重的，只要拿其中一个与其它好球称一次就可以确定了。
Got it. Thanks.
#19 Re: 做题了，12个小球，其中一个重量不同，天平称三次能不能找出这个球。
发表于 ： 2024年 4月 28日 12:35
由 nk
Bluesky 写了： 2024年 4月 28日 11:54
其实就两种，平衡或不平衡。引入左右就浪费称量次数了。你走到天平另外一边看，不平衡其实就是一种情况。
“知道一边的球比另一边的球更重” 获得的信息 比“两边的球重不相等” 要多一些信息的， 是三种情况。
#21 Re: 做题了，12个小球，其中一个重量不同，天平称三次能不能找出这个球。
发表于 ： 2024年 4月 28日 12:42
由 nk
Bluesky 写了： 2024年 4月 28日 11:57
错了。题目指异常球，并未说轻重。3次称量，不但要找出异常球，还要找出此球是轻于还是重于正常球
同意前半句，但不同意后半句，题目是要找出异常球就可以了，无须判断“此球是轻于还是重于正常球”。