李宗瑞里的贝贝是谁:一个很难的数学问题

其它2位的方法都需要知道不同的小球是重还是轻,如果不知道的话就不能4次称出来.而我的方法不需要知道这点,并不是题目少了条件.

1.天平两边各放4个,如果重量一样,则不同的小球剩下5个中.如果不一样则转第5步.

2.剩下5个球中每边放2个,如果一样,则最后那个球就是不同的小球(共称2次).如果不一样则继续转到第3步.

3.任取一边的2个小球放在天平2边,如果一样则不同的小球在这2个球中.如果不一样,则不同的小球在另2个小球中.

4.确定不同的小球在哪2个小球中后,取出其中1个和其它任意的小球(这2个以外的)放在天平2边,如果一样,则不同的小球就是剩下那个.如果不一样,则不同的小球就是放在天平上的那个(共称4次).

5.任取一边的4个小球,天平每边放2个,如果一样则不同的小球在另外4个球里面.如果不一样,则不同的小球在这4个小球里面.

6.确定了不同的小球在哪4个球里面后,按第3、4步做即可(共称4次).

称n次可以对付不多于（3∧n - 1）/ 2个球的情形 ！以下就这个结论，给出证明，与大家一起分享。
2.问题分析
基本思路包括两方面：
1． 我们把解决问题的过程看作由称量动作不断向系统引入信息，不断改变系统状态，直到可以找到坏球的过程，这样我们会首先考虑如何表示系统的状态和称量动作。如果对系统作完全的表示，分别记住对每个球所作过的称量操作，和分别记住每一次称量中在天平两端放了哪几个球，意义肯定不大，最好在遵循一定原则的基础上尽可能简单对称地表示系统，这些原则是为了确保不会有逻辑上的风险，为此，必须作到：
i. 所描述的状态和称量动作必须包含了实际上存在的每一种情况，确切说，每一种现实中的存在情况和每一个现实中可能发生的称量动作和称量结果必须能被确切表示。
ii. 对于每一种状态下每一种称量动作的每一种结果，必须能确知系统因此跳到了哪一种状态。
iii. 对于定义每一种状态，必须能确知她是否完成状态，即已经能准确无误地指出坏球的状态。
满足了这些条件，我们就可以放心地讨论下去。
2． 换一种方式去理解问题，我们不去具体解决某一个问题，或者说，不会就具体某个状态去求解，询问需要的称量次数，而是反过来询问，如果有了n次称量机会的话，可以求解出哪些状态。这样做是有好处的，因为n+1次称量能求解的状态集合显然依赖于n次的。

3．系统的表示
好，现在先来定义系统的状态，如下：我们把所有已经可以确切判断为标准球的球标上0，然后在剩下的球中，把所有未曾参加过称量的球标上∞，曾经在某次称量中位于重的一边的球标上1，曾经位于轻的一边的球则标上-1，当然，系统中永远就只有这4种球，我们就试图用这4种球的数量去表示系统的状态。
考虑一个问题，如果一个球曾经出现在重的一边，又继而出现在轻的一边，那把它标为1好还是-1好呢？答案是标为0，简单想想就明白了，如果它是坏球，它就永远只可能出现在一边，因为它就是使天平倾斜的原因，而它决不可能既比标准球重又同时比标准球轻，所以它就会在分类的第一步被标上0，因此这样的分类首先是可行的。
现在好很多了，系统中就只有4种球，而不再是标号着1到n的经历了各种复杂称量的球。我们来看一下，能不能把状态的表示作进一步的简化。
首先，我们知道，标准球所起的作用只是保证天平的两端有着相同数量的球，也就是说，对我们而言，只有数量足够与否的差别，但这会迫使我们只能采用较差的称量策略，这会严重破坏问题的对称性，为此我们打算先解决标准球够用的情况，运气非常好，弄清楚了这种情况后，就发现，其实只要有一个标准球，已经可以让我们在任何情况下都采用最优称量策略，这样，至少我们可以肯定从第二次称量开始，就有了足够的标准球。而问题的分类也特别的简单：是否有一个标准球，没有任何的中间情形。
现在可以用一个3维向量(x, y, z)来表示系统的状态，其中x，y，z分别表示系统中标为1，-1及∞的球的数量。我们还发现，标记∞的球和标记1或-1的球不可能同时存在，因为标记1或-1的球必定由不平衡的称量产生，我们考虑第一次这样的称量，我们已经可以肯定坏球在天平上并导致了天平的倾斜，所有不在天平两端的球就成了标准球，这时起，系统就不会再有标记为∞的球了。因此系统只有两种状态：要么只有一些标记为∞的球，可以表示为(0, 0, z)，要么只有标记为1或-1的球，表示为 (x, y, 0)我们知道系统的初始状态为(0, 0, z)，在经过若干次称量后可能会开始变为(x, y, 0)的形式。完成状态有(1, 0, 0)、(0, 1, 0)和(0, 0, 1)，为了讨论方便，我们把(0, 0, 0)也算作一种完成状态。
再来定义称量动作，考虑状态(x, y, z)，我们会怎样做呢？我们大概会把数量分别为x1、y2、z1的标记为1,-1和∞的球放在天平左边，然后把数量分别为x2、y1、z2的球放到右边，这样在天平下面还有x3、y3、z3个球，当然了：
x1 + x2 + x3 = x
y1 + y2 + y3 = y
z1 + z2 + z3 = z
我们把这样的称量记做((x1, y1, z1), (x2, y2, z2), (x3, y3, z3))，这也是我们所有可能的称量。天平可能平衡、左倾或右倾，分别记为：
((x1, y1, z1), (x2, y2, z2), (x3, y3, z3), 0)
((x1, y1, z1), (x2, y2, z2), (x3, y3, z3), 1)
((x1, y1, z1), (x2, y2, z2), (x3, y3, z3), -1)
在这3种结果下，系统的下一个状态分别是(x3, y3, z3)、(x1+z1, y1+z2, 0)和(x2+z2, y2+z1, 0)。
下面开始讨论n (n≥0)次称量能解决的状态集合，分情况讨论，有足够标准球情况下的得到的集合记为An, 没有标准球时得到的集合记为Tn。只有标记1、-1的球的情况下的子集分别记为Bn和Un，只有标记∞的球的情况下的子集记为Cn和Vn。

4.(x, y, 0)状态的情形
先来讨论(x, y, 0)的情形，称量策略为((x1, y1, 0)、(x2, y2, 0)和(x3, y3, 0))。考虑不同的称量结果，如果天平左倾，那么天平右边的x2个球和天平左边的y2的球都已经是标准球，天平下的x3和y3个球也已经是标准球，因此系统的状态成为(x1, y1, 0), 同样的，如果天平右倾，则系统状态成为(x2, y2, 0), 如果天平平衡，系统的状态就成为(x3, y3, 0)。
如果状态(x1, y1, 0)，(x2, y2, 0)，(x3, y3, 0) 都是可以用n次称量解决的，那么状态(x, y, 0)就已经可以用n+1次称量解决。由于考虑了所有的称量动作和相应的结果，所以事实上我们得到的是一个充分必要条件：状态(x, y, 0)可以用n+1次称量解决的当且仅当能找到一种分解方式，使状态(x1, y1, 0)，(x2, y2, 0)，(x3, y3, 0) 都可以用n次称量解决。也就是说:
Bn+1 = { b | b = b1 + b2 + b3 b1,b2,b3∈Bn}
------------------------a
我们还知道：
B0 = {(0, 0, 0), (1, 0, 0), (0, 1, 0)} = {(x, y, z) | x+y≤1, z=0}
-----------------------b
结合a，b，用数学归纳法可以得到：
Bn = {(x, y, z) | x+y≤3∧n, z=0}
------------------------c
再考虑没有足够标准球的情形，我们来说明：
Un = Bn ------------------------d
也就是说，在(x, y, 0)状态的情况下，标准球不会对称量次数造成影响。
下面来证明d：
显然U0 = B0，设Un = Bn，任给定 (x, y, 0) ∈ Bn+1, 有x + y ≤3∧(n+1)
作x = a + a + b，y = c + c + d
使 a ≤ b ≤ a + 1，c ≤ d ≤ c + 1，
容易验证，a + c ≤ 3∧n、b + d ≤ 3∧n
这样，作 x1 = x2 = a、y1 = y2 = c、x3 = b、y3 = d，由于x1 + y2 = x2 + y1，不借助标准球，就可以采用称量策略：
((x1, y1, 0), (x2, y2, 0), (x3, y3, 0))
显然(x1, y1, 0)、(x2, y2, 0)、(x3, y3, 0) ∈Bn = Un
这就是说，可以不借助标准球，用n+1次称量求解(x, y, 0)状态。因此(x, y, 0) ∈Un+1。
于是，Bn+1 ℃ Un+1，显然Un+1 ℃ Bn+1，即得 Un+1 = Bn+1。
5.(0, 0, z)状态的情形
下面再来解决(0, 0, z)的情形，称量策略为((0, 0, z1)、(0, 0, z2)和(0, 0, z3))。考虑不同的称量结果，如果天平左倾，系统的状态成为(z1, z1, 0)，天平右倾，系统状态成为(z2, z1, 0), 天平平衡，则系统的状态成为(0, 0, z3)。类似于前面的分析，我们知到：
Cn+1 = {(0, 0, z) | z = z1 + z2 + z3 (z1, z2, 0)∈Bn 或 (z2, z1, 0)∈Bn 并且 (0, 0, z3) ∈ Cn }
--------------------------------------------------------------e
由Bn的结构知道，e又可以简化为：
Cn+1 = {(0， 0，z) | z = z1 + z2 z1≤3∧n 并且 (0, 0, z2) ∈ Cn }
-------------------------------------------------f
容易知道:
C0 = {(0, 0, 0), (0, 0, 1)} = {(0, 0, z) | z≤1}
--------------------------------------------------g
综合f、g，用数学归纳法，可以得到：
Cn = {(0, 0, z) | z≤(3∧n + 1) / 2}
---------------------------------------------------h
前面说过，只要有一个标准球，就可以总是采用最好的策略，现在来证明这个结论，把只有一个标准球的情况下n次称量能求解的所有形如(0, 0, z)的状态的集合记为Dn，我们要证明Dn = Cn。
显然D0 = C0，设Dn = Cn，任给(0, 0, z) ∈Cn+1，有：
z ≤ (3∧(n + 1) + 1) / 2 = (3∧(n + 1) + 1) / 2 = 3∧n + (3∧n + 1) / 2
故存在z1、z2使z = z1 + z2 并且z1 ≤ 3∧n ，z2 ≤(3∧n + 1) / 2
作x、y使x + y = z1 和 x ≤y ≤x + 1，由于有一个标准球，可以采用策略：((0, 0, x), (0, 0, y), (0, 0, z2))
显然(x, y, 0)、(y, x, 0) ∈Bn，(0, 0, z2) ∈Cn
这就是说，有一个标准球，用n+1次称量可以求解(0, 0, z)状态。因此(0, 0, z) ∈Dn+1。
于是，Cn+1 ℃ Dn+1，显然Dn+1 ℃ Cn+1，即得 Dn+1 = Cn+1。
这说明了，有无数标准球的情况和有一个标准球的情况是没有区别的，对系统中的任意状态都一样。前面实际上已经解决了有一个标准球的情形：
Cn = {(0, 0, z) | z≤(3∧n + 1) / 2}
意思是说，n次称量能求解当且仅当球数不超过(3∧n + 1) / 2。
最后考虑没有标准球的情形，事情并不难办，由于没有标准球，第一次采用的策略只能是((0, 0, x), (0, 0, x), (0, 0, y))。因此系统就要么成为(x, x, 0)状态，要么成为(0, 0, y)状态，并且成了有标准球的情形。于是得到:
Vn = {(0, 0, z) | z = x + x + y (x, x, 0)∈Bn-1 并且 (0, 0, y) ∈Cn-1}
-------------------------------------------------h
由Bn和Cn的结构知道，h实际上就是：
Vn = {(0, 0, z) | z = x + x + y x+x≤3∧(n-1) - 1并且 y ≤(3∧(n-1) - 1) / 2}，于是得到：
Vn = {(0, 0, z) | z ≤(3∧n - 1) / 2}
-------------------------------------------I
意思是说，n次称量能求解当且仅当球数不超过(3∧n - 1) / 2。
最后分别给出在有一个标准球的情形下和没有标准球的情形下n次称量能求解的状态的集合，由前面分析知道，她们分别就是An和Tn。
An = Bn ∪ Cn
An = {(x, y, z)| x + y≤3∧n 且 z = 0 或 x = 0, y = 0, 且z≤(3∧n + 1) / 2}
---------------------------------------------------j
Tn = Un ∪ Vn
Tn = {(x, y, z)| x + y≤3∧n 且 z = 0 或 x = 0, y = 0, 且z≤(3∧n - 1) / 2}
---------------------------------------------------k

其实答案可以再简化很多，就是用已经称过的球数量x和没有称过的球数量y来表示状态。道理是一样的，关键是理解思路。有兴趣可以自己证明一下。

1)先分成3组,2组6个的放天平2边..如果2边平衡的话就是剩下1个是不同的.
2)如果2边不平衡,(是不是少个条件啊,那个小球是比其他的重还是轻)再分成每组2个,分3组.取2组放上天平.
当天平平衡,把剩下的2个去称第3次.
当天平不平衡,把不一样的那组拿出来,如果是1个比较轻的就是拿轻的1组称第3次,重的话拿重的称第3次.

先一边6个,等重就是剩的那个,不等重,把轻的拿下来,把重的那边一边3个,称后拿掉轻的那边,再把重的那边一边一个,要是等重就是剩的那个,不等就是重的那个.
这个办法比楼上的简单,次数也少,最可行了~

--------------------------------------------------------------------------------

1)先分成3组,2组6个的放天平2边..如果2边平衡的话就是剩下1个是不同的.
2)如果2边不平衡,(是不是少个条件啊,那个小球是比其他的重还是轻)再分成每组2个,分3组.取2组放上天平.
当天平平衡,把剩下的2个去称第3次.
当天平不平衡,把不一样的那组拿出来,如果是1个比较轻的就是拿轻的1组称第3次,重的话拿重的称第3次.

上面都不对的 都不符合题目 要么多称了 要么瞎改题目