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

[Bluesky]

当年做这个题目，做出后惊异于此题的严密逻辑。其实有多种方法，其实都是殊途同归。轻或者重，都是相对于正常球。而且3次称量后，是能得出异常球是轻还是重于正常球的。其实当时题目是这么要求的。
分组很重要，有两个支线。
第一次分组，是3组，每组四个。
第一次称量，只有2种情况，平衡，或者不平衡。
如果平衡，走第一支线：
异常球在第三组的四个球里面，起名异常球组。
异常球组里拿出一个球放在一边，用剩余的3个球和三个正常球进行第二次称量，结果只能是平衡或者不平衡。
如果平衡，那么异常球就是前面放在一边的那个。把这个异常球和任意一个正常球进行第三次称量，得出异常球是重于还是轻于正常球。
如果不平衡，那么从第二次称量，可以得知异常球到底是重于还是轻于正常球，但还未知异常球是这三个中的哪一个。
于是进行第三次称量：
这三个球拿出一个放在一边，把另外两个进行称量。结果只有平衡或者不平衡。如果平衡，那么异常球就是放在边上的那一个，而且我们已经从第二次称量里已经知道它是重于，还是轻于正常球。如果不平衡，因为我们已经在第二次称量中已经知道异常球是种还是轻于正常球，所以可以从不平衡里得知哪个是异常球。
以上是第一支线。
如果第一次称量不平衡，那么第三组的4个球都是正常球，异常球在前面两组里面，走第二支线。
第二支线比第一支线复杂些。

[nk]

当年做这个题目，做出后惊异于此题的严密逻辑。其实有多种方法，其实都是殊途同归。轻或者重，都是相对于正常球。而且3次称量后，是能得出异常球是轻还是重于正常球的。其实当时题目是这么要求的。
分组很重要，有两个支线。

我做了一下，12个球称三次以后，最后确实能够判断欻来坏球对于正常球是轻的还是重的。

但如果是13个球称三次，就无法判断出（至少我的做法）那个坏球对于正常球是轻的还是重的。

[tfusion]

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

14个球三次是可以的

分三组，5，5，4
如果两个5个球的组等重，那剩下的四个球2次可以找出，共3次

如果两个5个球的不等重，假设组1比组2重。
从组1里面拿两个球换到组2里面。这样又有几种情况：
1. 组1还是重。那不同的球是重球，而且在组1剩下没换的3个球里面。再称一次就可以找出
2. 组1比组2轻了。那不同的球是轻球，而且是换出去的两个球中的一个，再称一次可以找出。

总共3次

其实我上面的递归公式是正确的。我已经验证很多个数了。

[tfusion]

我做了一下，12个球称三次以后，最后确实能够判断欻来坏球对于正常球是轻的还是重的。

但如果是13个球称三次，就无法判断出（至少我的做法）那个坏球对于正常球是轻的还是重的。

看我对14个球的解法。

13个球类似

15个球就必须4次了

[nk]

14个球三次是可以的

分三组，5，5，4
如果两个5个球的组等重，那剩下的四个球2次可以找出，共3次

如果两个5个球的不等重，假设组1比组2重。
从组1里面拿两个球换到组2里面。这样又有几种情况：
1. 组1还是重。那不同的球是重球，而且在组1剩下没换的3个球里面。再称一次就可以找出
2. 组1比组2轻了。那不同的球是轻球，而且是换出去的两个球中的一个，再称一次可以找出。

总共3次

其实我上面的递归公式是正确的。我已经验证很多个数了。

你的是开始 ABCDE > FGHIJ

然后交换重新称
FGCDE ？ ABHIJ

比如 坏球就是 HIJ 中的一个，这样还是左边的组1更重，这样第一种情况下，无法判断坏球是重球，坏球也可以是轻球。

[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))，k<=(n-1)/2

f(1) = 0
f(2) = 1 //其实f(2)可以是0，因为任选一个球都可以。但是为了以后递归方程成立，f(2)=1更好
f(3) = 2
f(4) = 2
f(5) = 2
f(6) = 2
f(7) = 3
f(8) = 3
f(9) = 3
f(10) = 3
f(11) = 3
f(12) = 3
f(13) = 3
f(14) = 3
f(15) = 4
f(16) = 4

[tfusion]

你的是开始 ABCDE > FGHIJ

然后交换重新称
FGCDE ？ ABHIJ

比如 坏球就是 HIJ 中的一个，这样还是左边的组1更重，这样第一种情况下，无法判断坏球是重球，坏球也可以是轻球。

我的解放能在最少次数找出不同的球。但是不一定能知道是轻还是重。

不同的球是轻或者重是对称情况。
14个球，ABCDEFGHIJKLMN
组1，ABCDE，组2，FGHIJ，组3，KLMN

1. 称组1和组2. 三种情况
1.1 组1比组2重。
1.1.1 称ABCIJ和FGHDE。两种情况
1.1.1.1 ABCIJ比FGHDE重。说明要找的球重，而且在ABC中间。再称一次就找出来了。
1.1.1.2 ABCIJ比FGHDE轻，说明要找的球轻，而且在DE中间，再称一次就找出来了。
1.2 组1比组2轻
这种其实跟1.1是对称的。一样再称两次就找出来了。
1.3 组1和组2一样重
1.3.1 不同的球在KLMN里面。不知道轻重
1.3.1.1 称K和L。两种情况
1.3.1.1.1 K比L重。
1.3.1.1.1.1 再称K和M。如果K还重，K就是不同的那一个球，而且是重球。如果K和M等重，那么L是那个不同的球，而且是轻球
1.3.1.1.2 K和L一样重
1.3.1.1.2.1 称K和M。如果一样，N是不一样的那一个，但是不知道轻重。如果不一样，M是答案。同样不知道轻重


这样，3次就能找出那个球

[nk]

我还是写一个 12个球的答案吧

    
开始分成三堆（每堆4个），拿两堆出来比较
a: 一样重， 记第三堆的那四个球为 ABCD， 其余8个球为oooo oooo
   称重 AB  ？ Co
   a1: 如果一样重，坏球在D 里，把D 和 o 来比较就知道坏球是轻的还是重的
   a2: 如果 AB > Co, 坏球在A，B，C里,
      下一步 A？B，
      a2i: 如果  A!=B, 那么坏球是重球，而且是A和B比较出来的那个重球。
      a2ii:  如果  A==B, 那么C是坏球，也是轻球
   a3: 如果 AB < Co, 用a2 做类似的推理
b: 不一样重，记重的那一堆球是 ABCD， 轻的那一堆球是 EFGH， 即 ABCD>EFGH, 其余四个求是 oooo
   称重 ABE  ？ CDo
   b1: 如果一样重，坏球在FGH 里，并且坏球是轻球
      下一步 F？G， 就很容易判断出哪一个是坏球
   b2: 如果 ABE > CDo 那么E，C，D 不可能是坏球，坏球在 A,B里，而且环球是重球
      下一步 A？B， 就很容易判断出哪一个是坏球
   b3: 如果 ABE < CDo， 那么A，B 不可能是坏球，坏球在 C，D，E 里
      下一步C？D，
      b3i：如果 C!=D， 那么E不是坏球，  而且坏球是重球，而且是C和d比较出来的那个重球 
      b3ii：如果 C==D， 那么E是坏球，也是轻球
           
b的那一个分支也可以用 ABE ？ CDF 来做。

[water77]

球外形一样。

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

这是当年小学奥赛题
还更难的奇怪烧脑题
转魔方
等等


叔老了，现在不爱玩了
小刘也不爱玩这些

[wmwmw]

我的解放能在最少次数找出不同的球。但是不一定能知道是轻还是重。

不同的球是轻或者重是对称情况。
14个球，ABCDEFGHIJKLMN
组1，ABCDE，组2，FGHIJ，组3，KLMN

1. 称组1和组2. 三种情况
1.1 组1比组2重。
1.1.1 称ABCIJ和FGHDE。两种情况
1.1.1.1 ABCIJ比FGHDE重。说明要找的球重，而且在ABC中间。再称一次就找出来了。
1.1.1.2 ABCIJ比FGHDE轻，说明要找的球轻，而且在DE中间，再称一次就找出来了。
1.2 组1比组2轻
这种其实跟1.1是对称的。一样再称两次就找出来了。
1.3 组1和组2一样重
1.3.1 不同的球在KLMN里面。不知道轻重
1.3.1.1 称K和L。两种情况
1.3.1.1.1 K比L重。
1.3.1.1.1.1 再称K和M。如果K还重，K就是不同的那一个球，而且是重球。如果K和M等重，那么L是那个不同的球，而且是轻球
1.3.1.1.2 K和L一样重
1.3.1.1.2.1 称K和M。如果一样，N是不一样的那一个，但是不知道轻重。如果不一样，M是答案。同样不知道轻重


这样，3次就能找出那个球

1.1.1.1和1.1.1.2假设都不对。

[nk]

我的解放能在最少次数找出不同的球。但是不一定能知道是轻还是重。

不同的球是轻或者重是对称情况。
14个球，ABCDEFGHIJKLMN
组1，ABCDE，组2，FGHIJ，组3，KLMN

1. 称组1和组2. 三种情况
1.1 组1比组2重。
1.1.1 称ABCIJ和FGHDE。两种情况
1.1.1.1 ABCIJ比FGHDE重。说明要找的球重，而且在ABC中间。再称一次就找出来了。
1.1.1.2 ABCIJ比FGHDE轻，说明要找的球轻，而且在DE中间，再称一次就找出来了。
1.2 组1比组2轻
这种其实跟1.1是对称的。一样再称两次就找出来了。
1.3 组1和组2一样重
1.3.1 不同的球在KLMN里面。不知道轻重
1.3.1.1 称K和L。两种情况
1.3.1.1.1 K比L重。
1.3.1.1.1.1 再称K和M。如果K还重，K就是不同的那一个球，而且是重球。如果K和M等重，那么L是那个不同的球，而且是轻球
1.3.1.1.2 K和L一样重
1.3.1.1.2.1 称K和M。如果一样，N是不一样的那一个，但是不知道轻重。如果不一样，M是答案。同样不知道轻重


这样，3次就能找出那个球

这一步1.1.1.1 推理过不去。
你开始 ABCDE > FGHIJ
然后 ABCIJ > FGHDE, 不能说明坏球是重球， 因为坏球可以是轻球，在F，G, H里。

这一步只能推断出坏球不再 I，J，D,E 里，但坏球开可能在 A，B，C， F，G，H 里