13球称重问题

 转自：    http://hi.baidu.com/anuiz/blog/item/1cb7cc172fb0d100c93d6dad.html

13球称重问题是一个很经典的题, 原题大意为:
现在有13个小球,其中12个球重量相等只有一个球是坏球,与其他12个球的重量不相同,但不知道比正常球轻还是重. 请问如何使用天平(无砝码不能记录重量)在3次内判断出哪一个球是坏球.

网上有很多答案, 但有很多是错误的, 甚至有些人说13球问题在不知道坏球比好球轻还是重的情况下无解. 我可以很肯定的说13球问题是有解的并仔细验证过.

先卖个关子, 等待大家的答案.

我的方法(将小球编号1-13): STEP[1]: 1,2,3,4 v 5,6,7,8 如果平衡:  说明坏球在9-13内,则进行:
  STEP[2] 1,2,3 v 9,10,11 左盘全是好球,测试9,10,11
  如果相等说明坏球在 12,13中, 
     这样第3步随便拿一个好球与12相比就可以判断谁是坏球
     如果仍然相等,就判断不出坏球是轻还是重了,但仍知道谁是坏球
  如果不等,说明坏球在 9,10,11中,并且可以知道坏球是轻还是重. 
     这样第3步随便拿其中两个球,例如9,10称一下就能得出结论.
     相等则11是坏球;因为已知坏球是轻还是重,所以如果不等也可以轻易判断出哪个是坏球 如果第一步不平衡,说明坏球在1-8中; 9-13是好的球.于是:  STEP[2] 1,2,3,5,6 v 9,10,11,12,13 与第一步相比,这一步拿走了左边的4和右边的7,8, 把5,6挪到了左盘, 而右盘全部放好球.为什么是5个? 如果平衡: 坏球肯定就在拿走的4和7,8中了,并且不管是4,还是7,8都可以根据第一次测试判断坏球的轻重. 
  那第3步: 7 vs 8, 平衡则坏球是4;不平衡:则坏球肯定在7,8中,再根据第一步的结构就可以判断出坏球来.
   例如:若第一次是右边重,则坏球肯定是重的(因为第一步7,8就在右边嘛),于是第3步重的就是坏球.
如果不平衡: 就看测量结果是否与第一次一致了.
例如 第一次左边重, 第二次还是左边重, 那就说明坏球在1,2,3中, 并且比较重.一次就可以判断出来.
    如果第一次左边重, 第二次却变成右边重了, 还能说明啥, 说明5,6中有一个比较轻的坏球呗, 一次就可以判断出来.

OK, 答案貌似没问题, 不过问题来了:
1. 第一步是4v4, 为什么6v6不行? 3v3或5v5呢?
2. 这个解法是不是唯一解? 如果不是,那, 这个问题一共有多少个可行解?
3. 证明1,2 ---- 嗯,这样我才敢说这个答案不是凑出来的.

在回答这3个问题之前, 先来说一下与这个13球称重问题有关的一些数字:
1) 13球问题, 一共有26种可能的情况. (小球的编号有13种情况,而轻重是2种, 13*2=26)
2) 天平一次称量结果有3种情况(左偏,平衡,右偏), 3次称量最多有3^3=27种情况.

这两个数字说明3次确定出这26种情况是"有可能"的.(因为是整数... 总不能一次称4.333个球吧?呵呵)

看到下面caoamanno1的评论,跑出来回复下,呵呵

回复caoamanno1：你仔细想想,呵呵. 给出的方法中唯一判断不出坏球轻重的情况就是1,2,3,4=5,6,7,8 然后又 1,2,3=9,10,11,然后再1=12, 判断坏球是13, 但不知道轻重. 
4, 7,8的情况, 如你说的"可能情况是坏球4比较轻或者7,8中的那个坏球比较重", 不过这才称了两次, 下一次判断出来了.

题目本意就是要求判断出哪个球是坏球, 这样信息量就是log(2)(13),所以可以在3步内完成. 若是同时要求知道坏球是轻还是重的话, 信息量就增加一倍log(2)(13*2),3步测量所能得到的最大信息量理想值为log(2)(3*3*3),在现实情况下(离散的整数)可能根本做不到吧?

若要证明的确做不到的话,可以建模穷举解法,不过当时思路不清晰, 只是写了一个验证程序,26种情况都验证了没问题. 今天跟同事讨论的时候突然想通了,不过写出程序还要一段时间, 到时候再发博客讨论吧.