科学网—标签 - 称球问题

相关帖子	版块	作者	回复/查看	最后发表

热度 13 tianrong1945 2013-3-11 08:40

为完整起见并方便阅读，将上次的博文及续篇全文登载于此。我在帖子“大将军数学题 2- 答案”中，出了一道有关用老鼠检测毒药瓶的附加题：有 100 只一模一样的瓶子，编号 1-100 。其中 99 瓶是水，一瓶是看起来像水的毒药。只要老鼠喝下一小口毒药，一天后则死亡。现在，你有 7 只老鼠和一天的时间，如何检验出哪个号码瓶子里是毒药？这儿把它叫做‘ 问题 1 ’，解决此题的方法可谓二进制应用的经典：首先，将瓶子的 10 进制编号数改成 7 位的 2 进制码。然后，让第 1 只老鼠喝所有 2 进制码第 1 位是 1 的瓶子中的水；让第 2 只老鼠喝所有 2 进制码第 2 位是 1 的瓶子中的水；以此类推下去。这样，每个老鼠第二天的死活情况就决定了毒水瓶子二进制码这一位的数字：老鼠死，对应 1 ，反之为 0 。换言之，将 7 只老鼠死活情况排成一排。比如说结果是“死活死死活活死”的话，毒水瓶子的二进制标签就是： 1011001 ，转换成 10 进制，得到 89 。这道题可以有很多种在各个参数方向的扩张和一般化。最“通 - 通 - 通 - 通”的解够你研究好一阵子。比如，如果我们把题目稍加变化（问题 2 ）：有 100 只一模一样的瓶子，编号 1-100 。其中 99 瓶是水，一瓶是看起来像水的毒药。只要老鼠喝下一小口毒药，一天后则死亡。现在，给你 2 天的时间，请你告诉我，你至少需要多少只老鼠，才能检验出哪个号码瓶子里是毒药？比较原来的题目，这个题目有两个变化：一是给你的时间多了一天。因为老鼠喝毒药 1 天之后死去， 2 天意味着你可以做两次实验，这给了你一个时间方向（实验次数）的空间，有可能让你用更少数目的老鼠，达到同样的目的。第二个改变是提问的方式。这次的问题是：你‘至少’需要多少只老鼠？回答这类问题，是只要估计一个下限，对你来说，做实验的小白鼠多多益善，但你的老板要花钱买它们，他得考虑经济效益。当你还没有完全把方案想清楚之前，你好歹给老板一个交代呀。这种时候，信息论能派得上一点用场。刚才我说‘信息论’，实际上，我们完全用不上什么信息论的任何高深理论，用的只不过是由香农定义的计算信息量的一个公式而已。牛刀杀鸡虽然太大，但用它锋利的小尖给开个小口也未尝不可。不仅仅是这道题，还有几星期前科学网讨论热烈的“称球问题”，都是能用此‘牛刀’而有所受益的。实际上，我认为，许多问题的解决，都能和这‘牛刀’沾上边。如果从‘信息’的角度来分析某些问题，可以使你更登高望远，对问题能有更深层的理解，更容易融合各学科的间隙，达到借他山之石而攻玉的效果。科学（不仅限于数学）上的大多数研究，说穿了就是一个处理‘信息’的过程。摈弃无用的信息，想办法得到有用而正确的信息，用以消除原来课题中的不确定性，得到更为确定的科学规律。那么，我们首先要明白，什么是信息？这是一个古老的问题，又是一个现代的问题，也是一个迄今为止仍然众说纷纭、悬而未决的问题，特别是在社会所认可的广义信息的层面上。你要是问：“什么是信息？”，人人都能列出一大串他称之为‘信息’的东西：新闻、消息、音乐、图片……。然而如果问：“信息是什么？”那就难以回答了。因为你可以说：“音乐是信息”，但你不能说：“信息是音乐”；你可以说：“照片是信息”，但你不能说：“信息是照片”。要给信息下个定义是不容易的。‘信息’的定义需要从许多具体信息表现形式中抽象出它们的共性来。中国古人理解的信息其实很简单，正如李清照的名句中所述：“不乞隋珠与和璧，只乞乡关新信息。”，看来这只是通俗意义上的‘音讯’或‘消息’而已。现代人比较考究，注重科学。因此而成天琢磨：信息到底是什么？信息是主观的还是客观的？是相对的还是绝对的？昨天北京发大水，你将这个消息，用电话告知你南京的两个朋友，可是， A 说他早知此事， B 原来不知晓，因此，这条消息对 A 来说，没有增加任何信息，对 B 来说就增加了信息。 B 抱着的小狗好像也听见了电话中的声音，但它不懂人的语言，这对它来说也不是信息。信息是模糊的还是精确的？你走到树林里，艳阳高照、和风习习、桃红李白、燕飞鸟鸣，大自然传递给我们许多信息，这些算是没有精确度量过的、模糊的信息。信息和‘知识’是一码事吗？也应该不是。众所周知，我们的信息化社会虽然充满了信息，但其中“鱼龙混杂，良莠不齐”，以至于大家都希望自己的孩子不要整天沉迷于网上，许多人抱怨：“信息虽发达，知识却贫乏”。所以，信息并不等同于知识！文学家、哲学家、社会学家……，各家各派都对‘信息’ 有不同的理解和说法。这其中，物理学家们，是如何理解和定义信息的呢？物理学家们的研究对象是物质和物质的运动，即物质和能量。在他们看来，信息是什么呢？是否能归类进这两个他们所熟悉的概念呢？信息显然不是物质，它应该是物质的一种属性，听起来和能量有些类似，但它显然也不是能量。物理学中的能量早就有其精确的、可度量的定义，它衡量的是物体（物质）做功的本领。信息与这种‘功’似乎无直接关联。当然，我们又知道，信息是很有用的，个人和社会都可以利用信息来产生价值，这不又有点类似于‘做功’了吗？对此，物理学家仍然摇头：不一样啊，你说的好像是精神上的价值。信息属于精神范畴吗？那也不对啊，从科学家们的眼中看来，信息，仍然应该是一种独立于人类的主观精神世界、客观存在的东西。因此，到了最后，有人便宣称说： “组成我们的客观世界，有三大基本要素：除了物质和能量之外，还有信息。” 美国学者、哈佛大学的欧廷格（ A ． G ． Oettinger ）对这三大基本要素作了精辟的诠释： “没有物质什么都不存在，没有能量什么都不会发生，没有信息什么都没有意义。” 尽管对“信息是什么？”的问题难有定论，但通过与物理学中定义的物质和能量相类比，科学家们恍然大悟：信息的概念如此混乱，可能是因为我们没有给它一个定量的描述。科学理论需要物理量的量化，量化后才能建立数学模型。如果我们能将‘信息’量化，问题可能就会好办多了！于是，在二十世纪 40 年代后期，一个年轻的科学家，后来被人誉为信息和数字通讯之父的香农，登上了科学技术的历史舞台。香农的两大贡献：一是信息理论、信息熵的概念；另一是符号逻辑和开关理论。香农的信息论为明确什么是信息量概念作出了决定性的贡献。感谢香农，在定量研究的科学领域中，他将原来模模糊糊的信息概念，天才地给以了量化，使我们大家在解数学问题时也能‘牛刀小试’。其实香农并不是给信息量化的第一人，巨人也得站在前人的肩膀上。 1928 年，哈特利（ R.V. H. Harley ）就曾建议用 N log D 这个量表示信息量。 1949 年，控制论创始人维纳将度量信息的概念引向热力学。 1948 年，香农认为，信息是对事物运动状态或存在方式的不确定性的描述。并把哈特利的公式扩大到概率 pi 不同的情况，得到信息量的公式：　　 H= ∑ -pi log pi 如果计算中的对数 log 是以 2 为底的，那么计算出来的信息就以比特（ bit ）为单位。根据香农的信息概念，信息能消除不确定性，而我们在解决数学题的时候，也是要消除不确定性，得到确定的答案。并不仅仅是老鼠问题和称球问题如此，我认为大多数问题都多少是一个‘消除不确定性’ 的过程。因此，我们为何不借用香农的工具，研究研究我们的问题有多少不确定性呢？也就是说，需要多少信息量才能解决这个问题？另外，根据题目所限制的手段，最多能够得到多少信息量？有无可能完全解决这个问题？等等。具体到老鼠和毒药的问题。 100 瓶液体中 1 瓶有毒，每 1 瓶发生有毒的概率是 1/100 ，这时候要确定毒药瓶所需的信息量 H = -(p1logp1+p2logp2+….+p100logp100) 。因为所有瓶子完全相同，这是一个等概率问题， p1 = p2 =…=p100 = 1/100 。得到 H=-log （ 1/100 ）。下面计算从老鼠能得到的信息量。首先考虑问题 1 ，即给定时间为 1 天的情况。一天后，每只老鼠或死或活，因此，能够提供 1 比特的信息。 7 只老鼠则能提供 7 比特的信息。再看看刚才列出的确定毒药瓶所需的信息量 H 的公式： H=-log （ 1/100 ） -log （ 1/128 ） = 7 比特。因此，问题 1 应该可以解决。这个可能性是信息论提供给我们的。实际上，应该不仅仅是可能性，这种计算信息量比特数的方法能启发我们的思维。在解题时，学习别人解题的方法固然重要，而探讨别人是如何想到这种方法的，可能更为重要。在《大将军数学题 2 》的讨论中，就有博友说，如果提到 2 进制，此题就容易了。的确如此，如果不想到 2 进制，对此题往往好像有点束手无策，不知如何下手。我们再来讨论问题 2 。所需要的信息量 H 的计算是和问题 1 一样的。然而，从每只老鼠能得到的信息量的计算，却可能会有所不同。这儿我用了‘可能’两个字，是因为我们还丝毫未曾谈及如何解决这个问题 2 。问题 2 和问题 1 的差别是在于老鼠可以参加接连两次实验。问题 1 中，只能做一次实验时，老鼠有两种状态：死或活。因此它可利用的信息量是 1 比特。如果能做两次实验，两次实验中都有生死的可能性，仅就逻辑而言，老鼠有四种可能情况：生生、生死、死生、死死。但其中的第三种情形：死生，是不可能发生的，因为在第一天的实验中死了的老鼠，不可能在第二次实验后又活过来。所以我们要将第一天实验中死了的老鼠，排除在第二次实验之外。所以，对问题 2 ，老鼠有 3 种状态，每种状态的概率为 1/3 ，因此，从一只老鼠得到的信息量 S=- （ 1/3log （ 1/3 ） + 1/3log （ 1/3 ） + 1/3log （ 1/3 ）） = log （ 3 ）。如果将这儿的对数取以 3 为底的话，可以说成，每只老鼠能得到的信息量是一个 3 进制位（ trit ）。多少只老鼠才能使总信息量大于 log （ 100 ）呢？解方程： k*log(3)log(100) = 3**k100 ，可得到 k=5 。因此，至少要 5 只老鼠，这便是问题 2 的解。问题 2 直接所问的问题已经有了答案：实验至少需要用 5 只老鼠。况且，理论上来说，从 5 只老鼠能提供的最大信息量，转换到可能检验的最多瓶子数： 3**5 = 243 ，已经大大地超过了 100 ，余量很多，将这个数目提供给老板，问题不大。但是无论如何， 5 只老鼠到底能否判定出有毒的瓶子，还需我们想出具体检验的方案才成定论。因此，我们继续思考问题 3 （问题 2 的延伸）：在能做两次实验的条件下，如何找出有毒的瓶子？沿着刚才信息量计算的思路，问题 1 最优答案用 2 进制有关的实验方法得到；问题 2 中估计老鼠数目的下界时，用到了 3 进制。那么，在能做两次实验的条件下，找出有毒的瓶子的最佳方案是否与 3 进制有关？试试看吧。首先，将瓶子的号码转换成 5 位的 3 进制。为什么是 5 ？ 5 只老鼠？对，由于同样的原因，最大的号码 100 需要用‘ 5 位的 3 进制’来表示。这 100 个 5 位 3 进制码列表如下： 00000 ， 00001 ， 00002 ， 00010 ， 00011 ， 00012 ， 00020 ， 00021 ， 00022 ， ………… 10201 然后，第一次实验：从左到右：让第 1 只老鼠喝所有 3 进制码第 1 位是 2 的瓶子中的水；让第 2 只老鼠喝所有 3 进制码第 2 位是 2 的瓶子中的水；以此类推下去。这样，每个老鼠第二天的死活情况就决定了毒水瓶子 3 进制码这一位的数字是不是 2 ：老鼠死， 2 ；老鼠活， 1 或 0 。第一次实验中死去的老鼠没有白死，它的死决定了毒水瓶 3 进制码的这位数字是 2 ！虽然这个老鼠为 2 而牺牲了，但很幸运，这一位的数字也被决定了，我们也不再需要这只老鼠。嘿嘿，我们让这个老鼠作出了它的最大贡献，要不然，就不是最优化的方案了。第一次实验中没死的老鼠也没有白白地冒险，也为我们提供了信息：毒水瓶子 3 进制码的这一位的数字肯定不是 2 ！所以，我们可以将 3 进制码这位是 2 的瓶子去除，因为它们肯定无毒。然后…… 第二次实验：让没死的老鼠喝下所有 3 进制码的该位数字为 1 的瓶子中的水。这个老鼠一天后的死活情况便决定了毒水瓶子 3 进制码这一位的数字是 1 还是 0 ：老鼠死， 1 ；老鼠活， 0 。这个问题可以此类推地扩展成更一般的问题：假设有 n 个瓶子，其中 1 个瓶子中的水有毒，实验的小白鼠喝了毒水 1 天后死去，给你 i 天的时间， k 只老鼠。问 n 的最大值是多少？如何实验，才能检测出毒水瓶来。答案：有 i 天的时间，你可以做 i 次试验，因为死了的老鼠不能继续试验， i 次试验后，老鼠总共的可能状态有（ i+1 ）个：第 1 次就死去、第 2 次死、第 3 次死、……、第 i 次死、一直活着。能检测的最多水瓶数 n=(i+1)**k 。检测方法：将所有瓶子用 k 位的 (i+1) 进制数编码，然后，遵循上面所述 i=2 类似的过程， i 天之后，根据 k 个老鼠的状态，可以确定毒水瓶的 (i+1) 进制数值。通过用信息论解老鼠喝毒药的这个简单练脑题，说明科学思维方法之重要性。作为信息论应用于数学题的另一个例子，再来分析“称球”问题。称球问题是说，用天平称 k 次，在 n 个球中找出唯一的一个重量不标准的次品球来， n 最大是多少？如何找？有关这个次品球的说法，通常有 3 种变形： 1. 已知次品球是更轻（或更重）； 2. 不知次品球的轻重，找出它并确定轻重； 3 、不知次品球的轻重。利用信息熵的概念，可计算出这 3 种情形下 n 的最大值，并且帮助思考构成算法的过程： 1. 已知次品球是更轻（或更重），这时 n 的最大值 = 3**k ； 2. 不知次品球的轻重，找出它并确定轻重，这时 n 的最大值 = （ 3**k-3 ） /2 ； 3 、不知次品球的轻重，这时 n 的最大值 = （ 3**k-1 ） /2 。下面首先分析第 1 种问题。为解释起来更为直观，设定 k=3 。换言之，我们的问题是：如何用天平称 3 次，从 27 个球中找出唯一的那个稍轻的球？ 27 个球中只有 1 个球稍轻，可能发生的情形为 27 种，每个球为次品的概率是 1/27 。类似于上面所说老鼠试药的问题，要确定是‘哪一只’老鼠，所需的总信息量 =log27 。在此题中的判定手段，限制了是天平。那么，天平每称一次，最多可以提供多少信息量呢？或者是说，可以为解题消除多少不确定性？天平称一次后，有 3 种结果：左轻右重（ A ）、左重右轻（ B ）、平衡（ C ）。因此，称一次所消除的不确定性 =log3 。接连称 3 次后，所消除的不确定性 =3*log3= log27 。根据刚才的分析，这个问题中，判定轻球所需的信息量与天平称 3 次能获得的信息量刚好相等。因此，用最佳的操作方法，有可能解决这个问题。既然从信息论作出的估算给了我们解决问题的希望，我们就试试看吧。天平似乎与 3 进制有关，我们便首先优选 3 进制。将 27 个球贴上 3 进制码的标签： 000 、 001 、 002 、 010 、 011 、 012 、 020 、 021 、 022 、 100 、 101 、 102 、 110 、 111 、 112 、 120 、 121 、 122 、 200 、 201 、 202 、 210 、 211 、 212 、 220 、 221 、 222 。将 3 进制码中，第 1 位（左）为 0 的 9 个球放天平左边，第 1 位为 1 的 9 个球放天平右边，称 1 次。如果天平平衡，则次品球 3 进制码第 1 位是 2 ；左轻右重，第 1 位是 0 ；左重右轻，第 1 位是 1 。总而言之，称这一次，确定了次品球 3 进制码第 1 位的数字。接下去，继续称，逐次确定次品球 3 进制码各位的数字，问题解决了。这个第 1 类问题不难推广到任意 k 的情形。下面再分析第 2 类称球问题：次品球不知轻重，最后需确定轻重的情况，具体来说就是，天平称 3 次，要找出 12 个球中那个唯一的又‘不知轻重’的次品球。将两个问题对比一下，共同之处是都用天平，因此，天平称 3 次能提供的最大信息量仍然是 log27 。不同之处是如何计算找出次品球所需要的信息量。因为现在要找出的次品球‘不知轻重’，因此，对每个球来说，不确定性增多了，这也是能判定的球的数目大大减少了（从 27 变到 12 ）的原因。现在，考虑这 12 个球，其中一个是或轻或重的次品的各种可能性。如果这个球是‘轻’的次品，记为 - ，‘重’的次品，记为 + ，因此，可能的次品分布情况： 1+ 、 1- 、 2+ 、 2- 、……、 12+ 、 12- 。共 24 种情形，所需要的信息量则为 log24 。这个值小于天平称 3 次所能提供的最大值，所以，可能有解，那我们就试试看吧。有人说，你用什么信息论扯了半天，最后还是要一个一个地列举，那你这信息论不是多余的吗？科学定律是客观的，但各人的观点却是见仁见智的，我不需要去强人所难，也并非想比较解称球问题各种方法孰好孰坏，孰优孰劣，只是想将信息论用于分析此题，如此而已。将 12 个球作如下编码：（ 000+ ， 000- ）、（ 001+ ， 001- ）、（ 010+ ， 010- ）、（ 011+ ， 011- ）、（ 100+ ， 100- ）、（ 101+ ， 101- ）、（ 110+ ， 110- ）、（ 111+ ， 111- ）、（ 200+ ， 200- ）、（ 201+ ， 201- ）、（ 210+ ， 210- ）、（ 211+ ， 211- ）、这儿，除了抽取了部分 3 进制的编码之外，还对每个球都给贴上了（ + 、 - ）两个标签，以表明此球‘或轻或重’而成为次品的两种可能性，也可等效于另一层编码。然后，将第 1 位为 0 的 4 个球（第 1 行）放天平左边，第 1 位为 1 的 4 个球（第 2 行）放天平右边，称第 1 次。 1 如果天平左轻右重，这也许是第 1 行中的某个球轻了、或是第 2 行中某球重了而造成的： 000- 、 001- 、 010- 、 011- 、 100+ 、 101+ 、 110+ 、 111+ 。 2 反之，如果天平左重右轻，也许是第 1 行中的某个球重、或是第 2 行中某球轻而造成的： 000+ 、 001+ 、 010+ 、 011+ 、 100- 、 101- 、 110- 、 111- 。 3 如果天平平衡，则次品球在第 3 行的‘ 毫不知轻重 ’的 4 个球（ 200 、 201 、 210 、 211 ）中。虽然是 4 个球，仍然有 8 种可能性： 200+ 、 200- 、 201+ 、 201- 、 210+ 、 210- 、 211+ 、 211- 。前面两种情形类似，都是将次品球限制到了 ‘ 半知轻重 ’的 8 个球中。所谓半知轻重，是因为该球有一个已经确定的附加标签（ + 或 - ）。比如说，编码为（ 000- ）的球是个‘半知轻重’的球，而编码为（ 000 ）的球是个‘毫不知轻重’的球。对（ 000- ）来说，尽管尚未确定此球是否是次品，但有一点是明确的：如果它是次品的话，它只能是更轻的次品。而球（ 000 ）则有‘轻重’两种次品的可能性。因此，‘半知轻重’球比‘毫不知轻重’球少了一半的不确定性。判定所需的信息量也成为一半。天平不平衡的情形，问题成为，“称 2 次从这 4 个半知的‘轻球’，及 4 个半知的‘重球’中找出次品球”的问题。为此，取 2 个轻球加 1 个重球放天平的一边，另 2 个轻球加 1 个重球放天平的另一边。称第 2 次之后便将问题归为称 1 次从 3 个半知轻重球中找出次品的问题。这个问题在 David J.C. MacKay 信息论的书中有叙述，借他的图表贴在下面。其中称球的过程看得很清楚，所以不再赘述。指出一点：在天平平衡的情形，称第 2 次时，需要用到称第 1 次后确定的标准球，即天平上的 8 个球。标准球是能够提供信息的，每个标准球在每次称量中最多能提供 1 比特的信息。下面再对第 3 类称球问题稍加分析，就是，天平称 3 次，要找出 13 个球中那个唯一的又‘不知轻重’的次品球的问题。类似于第 2 类问题，将 13 个球作如下编码：（ 000+ ， 000- ）、（ 001+ ， 001- ）、（ 010+ ， 010- ）、（ 011+ ， 011- ）、（ 100+ ， 100- ）、（ 101+ ， 101- ）、（ 110+ ， 110- ）、（ 111+ ， 111- ）、（ 200+ ， 200- ）、（ 201+ ， 201- ）、（ 210+ ， 210- ）、（ 211+ ， 211- ）、（ 222+ ， 222- ）、与第 2 类问题不同的是天平平衡的情况。这时需要从 5 个球， 10 种状态中找出次品：（ 200+ ， 200- ）、（ 201+ ， 201- ）、（ 210+ ， 210- ）、（ 211+ ， 211- ）、（ 222+ ， 222- ）将 5 球中的 3 个放在天平一边， 3 个标准球放另一边。天平不平衡情形的最后一次称法与第 2 类问题同，不同的又是天平平衡时的情形。天平平衡的情形，留下了 2 个不知轻重的球。因为我们有标准球可用，取 2 个待定球中的任何一个与标准球比较，如果不平衡，此球则为次品，并知其轻重；如果平衡，另 1 球为次品，但不能判定其轻重。读者可能注意到了，在上面两个用信息熵方法解数学题的例子中，我们经常说：“使用最佳方案”，只有使用最优化的操作方法，才能达到信息论所预期的上限。这儿所说的最佳方案，与信息论中的“最大信息熵原理”有关。什么是最大信息熵原理？它来自于热力学及统计物理中的熵增加原理。要讲清楚这个问题需要太多篇幅，在此只简单地科普一下。用通俗的话来说，最大信息熵原理就是当你对一个随机过程不够了解时，你对概率分布的猜测要使得信息熵最大。熵最大就是事物可能的状态数最多，复杂程度最大。换句话说，对随机事件的预测要在满足全部约束条件下，保留各种可能性。比如，你的女朋友叫你猜猜她的生日是哪一个月？如果你曾经看过她出生不久的照片，是秋天，那你可以猜测她生日是夏季的几率比较大；如果你对此完全没有概念，你就最好是对一年中的每一个月都一视同仁，给予相同的可能性。另一个例子是买股票投资的时候，专家会建议你买各种类型的不同股票。 “不要把鸡蛋放在一个篮子里！”投资专家说。这句话的意思，其实就是警告你要遵循最大熵原理，对难以预测的股票市场，最好的策略是尽可能多地保留各种可能性，才能降低预测的风险。在本文中所举的老鼠毒药问题中，尽量让每个老鼠试喝相等数目瓶子的水；在称球问题中，尽可能使天平‘左、右、下’的球的数目相等，这都是考虑最大信息熵原理而选择的最优策略。参考资料： David J.C. MacKay book ：“ Information Theory, Inference, and Learning Algorithms ”

23584 次阅读|20 个评论

根据对称性原理解决“称球问题”

热度 2 大毛忽洞 2013-2-9 11:36

根据对称性原理解决“称球问题” 称球问题定义解读（以13球为例）：有13个球，其中12个球是正品，1个是次品。所有正品球的质量相同，次品球和正品球的唯一差别是质量不同。从外表看，正品球和次品完全相同，其唯一的差别是质量差别，因此可以用天平来区别。如果正品球的质量为M，次品球的质量为M ’ ，则有M≠M ’ （这意味着：M＜M ’ 或 M＞M ’ ）。如何用天平来识别出次品球呢？正品球和次品球的质量都是未知数，但是M≠M ’ 可以用天平判断。例如：如果在天平两边放置 6 个球， 2 × 6 ＝ 12 ，手里剩下 1 个球。如果天平平衡，则次品就在手里，找到了次品球。显然，这种方法需要使用 13 次天平才能 100 ％把次品球找到。如果采用巧妙的方式在天平上摆放球，则只需要 3 次使用天平就可以 100 ％地把次品球找到。这就是所谓的应老师说的“ 4 － 4 － 5 ” 方式。如果是 14 个球，无论如何巧妙地摆放球，仅仅使用 3 次天平不可能 100 ％地找到那个次品球。现在把问题反过来说： 3 次使用天平，可以判断出 13 个球中的 1 个次品。换句话说： 3 次使用天平，可判断球的数量为 13. 4 次呢？ 5 次呢？这不，俺一口气，给出了 100 次的可判断数量，是个天文数字！无巧不成书， 400 年前开普勒玩球的堆垛，开启了数学堆垛的山门，为信息纠错码奠定了理论基础。毫无疑问，球的堆垛还是个地地道道的对称性问题。 400 年：开普勒猜想、数学堆垛和信息纠错码（科学网博文，可点击阅读，写于 2009 年）好了，借助 400 年前开普勒的球堆垛问题，把话题转到了对称性了。平衡就是对称，失衡则是对称破缺。俺的具体计算过程，是在对称原理框架下求解代数方程，然后对“次品嫌疑”出现的概率求和，并且要等于 1 。先把计算结果（计算机输出格式）贴出来晒晒太阳。 ^_^ 3,"次","可判断球数量=",13 4,"次","可判断球数量=",53 5,"次","可判断球数量=",117 6,"次","可判断球数量=",245 7,"次","可判断球数量=",501 8,"次","可判断球数量=",1013 9,"次","可判断球数量=",2037 10,"次","可判断球数量=",4085 11,"次","可判断球数量=",8181 12,"次","可判断球数量=",16373 13,"次","可判断球数量=",32757 14,"次","可判断球数量=",65525 15,"次","可判断球数量=",131061 16,"次","可判断球数量=",262133 17,"次","可判断球数量=",524277 18,"次","可判断球数量=",1048565 19,"次","可判断球数量=",2097141 20,"次","可判断球数量=",4194293 21,"次","可判断球数量=",8388597 22,"次","可判断球数量=",16777205 23,"次","可判断球数量=",33554421 24,"次","可判断球数量=",67108853 25,"次","可判断球数量=",134217717 26,"次","可判断球数量=",268435445 27,"次","可判断球数量=",536870901 28,"次","可判断球数量=",1073741813 29,"次","可判断球数量=",2147483637 30,"次","可判断球数量=",4294967285 31,"次","可判断球数量=",8589934581 32,"次","可判断球数量=",17179869173 33,"次","可判断球数量=",34359738357 34,"次","可判断球数量=",68719476725 35,"次","可判断球数量=",137438953461 36,"次","可判断球数量=",274877906933 37,"次","可判断球数量=",549755813877 38,"次","可判断球数量=",1099511627765 39,"次","可判断球数量=",2199023255541 40,"次","可判断球数量=",4398046511093 41,"次","可判断球数量=",8796093022197 42,"次","可判断球数量=",17592186044405 43,"次","可判断球数量=",35184372088821 44,"次","可判断球数量=",70368744177653 45,"次","可判断球数量=",140737488355317 46,"次","可判断球数量=",281474976710645 47,"次","可判断球数量=",562949953421301 48,"次","可判断球数量=",1.12589990684261E+15 49,"次","可判断球数量=",2.25179981368524E+15 50,"次","可判断球数量=",4.50359962737049E+15 51,"次","可判断球数量=",9.00719925474098E+15 52,"次","可判断球数量=",1.8014398509482E+16 53,"次","可判断球数量=",3.6028797018964E+16 54,"次","可判断球数量=",7.20575940379279E+16 55,"次","可判断球数量=",1.44115188075856E+17 56,"次","可判断球数量=",2.88230376151712E+17 57,"次","可判断球数量=",5.76460752303423E+17 58,"次","可判断球数量=",1.15292150460685E+18 59,"次","可判断球数量=",2.30584300921369E+18 60,"次","可判断球数量=",4.61168601842739E+18 61,"次","可判断球数量=",9.22337203685478E+18 62,"次","可判断球数量=",1.84467440737096E+19 63,"次","可判断球数量=",3.68934881474191E+19 64,"次","可判断球数量=",7.37869762948382E+19 65,"次","可判断球数量=",1.47573952589676E+20 66,"次","可判断球数量=",2.95147905179353E+20 67,"次","可判断球数量=",5.90295810358706E+20 68,"次","可判断球数量=",1.18059162071741E+21 69,"次","可判断球数量=",2.36118324143482E+21 70,"次","可判断球数量=",4.72236648286965E+21 71,"次","可判断球数量=",9.44473296573929E+21 72,"次","可判断球数量=",1.88894659314786E+22 73,"次","可判断球数量=",3.77789318629572E+22 74,"次","可判断球数量=",7.55578637259143E+22 75,"次","可判断球数量=",1.51115727451829E+23 76,"次","可判断球数量=",3.02231454903657E+23 77,"次","可判断球数量=",6.04462909807315E+23 78,"次","可判断球数量=",1.20892581961463E+24 79,"次","可判断球数量=",2.41785163922926E+24 80,"次","可判断球数量=",4.83570327845852E+24 81,"次","可判断球数量=",9.67140655691703E+24 82,"次","可判断球数量=",1.93428131138341E+25 83,"次","可判断球数量=",3.86856262276681E+25 84,"次","可判断球数量=",7.73712524553363E+25 85,"次","可判断球数量=",1.54742504910673E+26 86,"次","可判断球数量=",3.09485009821345E+26 87,"次","可判断球数量=",6.1897001964269E+26 88,"次","可判断球数量=",1.23794003928538E+27 89,"次","可判断球数量=",2.47588007857076E+27 90,"次","可判断球数量=",4.95176015714152E+27 91,"次","可判断球数量=",9.90352031428304E+27 92,"次","可判断球数量=",1.98070406285661E+28 93,"次","可判断球数量=",3.96140812571322E+28 94,"次","可判断球数量=",7.92281625142643E+28 95,"次","可判断球数量=",1.58456325028529E+29 96,"次","可判断球数量=",3.16912650057057E+29 97,"次","可判断球数量=",6.33825300114115E+29 98,"次","可判断球数量=",1.26765060022823E+30 99,"次","可判断球数量=",2.53530120045646E+30 100,"次","可判断球数量=",5.07060240091292E+30 相关阅读： http://blog.sciencenet.cn/home.php?mod=spaceuid=826653do=blogid=658533 称球问题的通解

个人分类: 魔方和隐喻：也有老虎|3468 次阅读|3 个评论

六人集会问题

热度 6 xying 2013-2-4 08:52

好的智力游戏，挑战的是智力而不是知识，简单直观有确定的答案，但有一定的难度。问题的解决，不仅有征服高峰的快感，还常有开拓眼界的收获。上一个帖子“称球问题”就属于这一类。我这里再出一道题。为了让大家有收获，先给一个思路。我所学的许多知识中大约最直观的就是“ 抽屉原理 ”【 1 】了。它是组合数学的一个基本原理，最先是由德国数学家狄利克雷明确地提出来的，因此，也称为狄利克雷原理。这原理形象的说法是：将 10 个苹果放在 9 个抽屉，至少有一个抽屉会有 2 个或以上的苹果。如此等等，总之傻子都能明白的道理。把苹果换成鸽子，这原理也就叫“鸽巢原理”了。其实我在上面称球问题【 2 】的定理证明【 3 】中就几次用到抽屉原理，用决策树分析区分球的上限时也用过。只不过不说，人人也不打磕地通过了。这抽屉原理，用信息也能给出个解释，不过组合数学觉得用集合论就能说明白，就不用它来包装了。抽屉原理如果没有个不寻常的应用，那也没人会认这个账，早让奥卡姆的剃刀给切去了。下面题目，给大家一个验证的机会。 1958 年 6/7 月号的《美国数学月刊》上有这样一道题目：证明在任意 6 人的集会上，有 3 个人以前彼此都相识，或者有 3 个人以前彼此不相识，这两者必居其一。这道题的数目有限，自然可以用枚举法证明。但用抽屉原理，几句话就能说清，你知道该怎么证明吗？别看这道题简单，六人集会问题是组合数学中著名的拉姆塞定理的一个简单特例，它的思路可以得出另一些深入的结论。它们构成了组合数学中的“ 拉姆塞理论 ”【 4 】。 ××××× 你想出证明了吗？要是没有，下面是证明。在 6 人中任选一人（称为主人），他与其他 5 人的关系可以分成两类：认识的和不认识的。 5 人分 2 类，至少有一类是 3 人以上（抽屉原理）。假设主人认识的至少有 3 人，这 3 人如果互相全不认识，就满足问题中后一条件。否则，至少有两人认识，再加上主人，就有了互相认识的 3 个人，满足前一条件。因此，两条件必居其一。假设不认识的起码有 3 人，将前一假设论中“认识”与“不认识”的文字互换，完全对称地可以证明了结论。证毕。不过瘾，是不是？再出道题给大家思考。一个聚会中，大家见面握手。有人热情，有人冷淡，不见得都握的一样多。证明一定有两个人与一样多数量的人握了手。可能有讲究数学严谨性的人说：这题目不成立！反证法：要是聚会只有主人一个人，其他都没来，怎么有两个人握手的次数一样？ Q. E. D. 很幽默吧。在分 13 球的讨论中，也有类似的评论。有人说：这些球是玻色子，所以所有的那些解法都不成立，这提法还附有深入浅出的穷举法反证，以示严谨。我起先以为有人把四月一日的帖子发早了，后来见一再提醒大家，且有博文把问题“重新准确描述：有十三个球大小颜色形状完全相同，”还真叫人语塞。我更郁闷的是：这么多年，这么多人都兴致勃勃，绞尽脑汁地奔着这难题想，莫非还真有聪明人叫破了：“这是忽悠小孩子的皇帝新衣”？研读了一下，发现除了“玻色子”这词对小朋友有点难度外，这提法还真是善待小孩了。查了物理大辞典，“玻色子”在这儿的意思是：这些球外表不可区分，也就是说你把它们混着搁在一堆里，就认不出不同的出处了，所以别费心思在一堆里做什么组合。把这意思告诉小朋友，还真是个个雀跃，齐声说：以前都被忽悠了！为什么？好解了呀！ 13 个玻色子球，就有那么少数几个分堆的法子，不费脑筋考虑各种组合的效益，小朋友用穷举试几次也发现了 3 次是不可能分出次品。给自己压任务，琢磨称 4 次， 4 、 4 、 5 三堆一分，太容易了。实际上称 4 次都能分 31 个玻色子球，你让他分 13 个，差生都得满分。太没有挑战性了，这也叫智力题？难怪大人都不理会什么玻色子解释了。把分 13 球，或者 12 球的问题换成从玻色子球里挑出一个次品，除了这名词比较牛以外，真是没什么技术含量。把好好的一个挑战智力的问题变成乏味的儿童题。那是缺乏做事的常识了。其实真要别出机枢，在网上想整出点动静来，也不是没办法，比如说玩一篇从玻色子球中找出一个次品的通解。你看哈，既然在一堆里不能区分哪个从哪里来，那就别费心思颠来换去地组合，光考虑数量就行了。如果已经知道了次品是轻还是重，称 k 次可分 3**k （ 3 的 k 次方）球。如果未知轻重但外边有足够的正品球，称 k 次可分（ 3**k - 1 ） /2 个球而且知道了次品的轻重。证明？用数学归纳法， k=1 没问题；将 3**(k-1) 个球与正品球上天平比较，如果不平衡就知道了次品在这儿也知道它的轻重，再称 k-1 可解决；如果平衡，再称 k-1 次可解决天平外的（ 3** （ k-1 ） - 1 ） /2 个，加起来就对了。注意到这也同时分辨出次品的轻重。如果不求这轻重，再多搁一个在外边也成。好了，现在从不知次品轻重也没有正品球的起点开始，考虑怎么称 k 次。一开始把球分 3 堆，把两堆 3**(k-2) 个球上天平，如果不平衡，确定了外边是正品球，数出 3**(k-2) 个球把在天平上右边那些球换下来，再称，就能判断出次品是在原来天平哪一边了，而且知道次品是轻了还是重了。由上面分析可知，这样再称 k-2 次就能在这些球中判断出次品，且知轻重。第一次称时天平外有多少？（ 3** （ k-1 ） - 1 ） /2 个。如果第一次天平平衡，知道天平里都是正品了，用这些量外边这些球，由上面分析可知，称 k-1 可解决。注意到无论天平平衡不平衡，我们手里都是有充分的正品球。把这些数加起来，一共是 3** （ k-1 ） + （ 3** （ k-2 ） -1 ） /2 个，如果不要求判断次品的轻重，还能多出一个。这样称 2 、 3 、 4 、 5 次，可分 3 、 10 、 31 、 94 个玻色球，并知道次品轻重。或对不在乎次品轻重的能分 4 、 11 、 32 、 95 个。这是结构性证明，读了就知道该怎么操作了。。。这通解虽然没什么难度，如果用它垫底，再侃些什么玻色子球，借已有定论的东西炒作一下，马马虎虎算是沾着点技术含量，写反调文章才比口水帖强。玩游戏读文章做研究时，如果其中有歧义，聪明的人都会往有意义的方向想，而不会将它平庸化。这在玩游戏时是如此，做研究读论文时更应该如此。我在念研究生时，有个学弟，读到很经典论文证明中的一处错误，兴奋得不能自已。大家听了动静过来瞄一眼，都不吱声走开。我看久了实在不忍心，对他说：“这明显是一处笔误，大家最多只愣几分钟都顺过去了，就你还停在这儿。” 好了，大家也别停在这儿，那聚会握手题会解吗？会的，写个再罗嗦也不得超过 150 字的证明到评论里。【参考资料】【1】百度百科，抽屉原理 http://baike.baidu.com/view/8899.htm 【2】科学网博文，称球问题 http://blog.sciencenet.cn/home.php?mod=spaceuid=826653do=blogid=657778 【3】科学网博文，称球问题的通解 http://blog.sciencenet.cn/home.php?mod=spaceuid=826653do=blogid=658533 【4】维基百科，拉姆齐定理 http://zh.wikipedia.org/wiki/%E6%8B%89%E5%A7%86%E9%BD%90%E5%AE%9A%E7%90%86

个人分类: 智力|15837 次阅读|12 个评论

称球问题的通解

热度 13 xying 2013-2-1 12:36

称 13 球问题十分经典，就我所知也有三十多年历史了。因为问题简单，不需要预备知识，又有点难度，纯凭清醒脑力来解答，成为大人小孩通杀经久不衰的练脑题，聪明的中学生纸上画画也能解出，大人也就考究个虚空冥想，心智澄明的功力。这问题网上有不少答案，恐怕连中学生都知道了。喜欢做研究的人，就会考虑一般性的问题。在除了一个重量不同的次品外，其他等重的一堆球中，用天平称 k 次找出来，问这堆球最多可以是多少？它的通解是：最多可以达到 n = （ 3**k-1 ） /2 个球。这里 3**k 意思是 3 的 k 次方。我曾将这证明贴在外面的网上，很多人都看过了，现在附在后面。在科学网写科普，要有点技术含量的新意，才对得起愿意动脑筋看帖子的人。我就在这里分享考虑问题的思路。首先考虑一个简单的情况，假如已知这个次品比正品重（或轻），把这堆球三等分，放两堆到天平两边称一次可以指出是在哪一堆，一直重复这三等分法，就能确定是哪一个。所以称 k 次可以分辨 3**k 个球。有人从信息的角度解答这简单题。从 n 个球中取出次品的概率是 1/n ，确定它需要 log2(n) 比特的信息量；用天平称会有三种结果：左重右轻、平衡、左轻右重，称一次给出的信息量是 log2(3) ；所以从 n 个球中找出次品，需要称的次数 k 是 log2(n)/log2(3)=log3(n) ，也就是 n = 3**k ，这和上面的答案是一样的。对于不知次品轻重的情况，从 n 个球中取出次品的概率是 1/n ，而这次品是偏重或偏轻的概率是 1/2 ，确定它需要 log2(2n) 比特的信息量。所以从 n 个球中找出次品需要称的次数 k 至少是 log2(2n)/log2(3)=log3(2n) ，也就是 2n = 3**k ，考虑到左边是偶数，右边是奇数，故有 n = （ 3**k-1 ） /2 ，这和通解的答案是一样的。这个信息量说法看起来很牛，既简练又准确。但是做研究，每一步必须有根据，所有说法要落到实处，一直追查到逻辑上没有含糊之处才算完。我们首先要问：为什么可以应用这信息的计算？这球的信息量和天平的信息量是怎么联系起来？ “信息论中的编码理论呀！”好。那我们就要考究怎么把这问题转化为编码问题。对于简化问题，把这球排成一列，每次称时相当于编码数字的位置，判断次品属于哪一堆相当于给这位置赋值，从而可以给这列球编号，这构造了编码的模型，当然可以用信息量来解。为了说明可以应用编码的概念，其根据是天平称量把球区分成 3 堆的分类法。这是绕了一圈来说问题，这里的信息论编码只是用来装饰，除了看起来比较高深以外，对解题没有多大帮助，还不如直接用分类法解来得更直观。对于一般问题，怎么用几次天平称量的状态给这 2n 种的可能性编码？天平只能作用在物理的球上，每个球联系着两种的可能，在天平的两边必须放等量的球，所以考虑编码还必须受到物理实现的约束。不考虑这些细节，没办法构造编码的数学模型。直接套用信息量计算的公式看起来很牛，虽然结果也对。但深思下去就觉得这个步子迈得太大，缺乏说服力。我举个例子来提疑问。大家知道对于 5 个球，用天平称两次是没有办法从中区分出次品球。这用信息量的解释是： 5 个球其中有个次品不知偏重或轻，信息量是 log2(10) ，称两次信息处理能力是 2log2(3)= log2(9) ，当然是不能区分。但是，我们如果加上一个已知的正品球，就能够区分了。（这个解法见《称球问题》帖子和下面决策树，其中放外边那堆 5 个球的称法，或后面通解的证明）需知这个已知的球信息量是 0 ，加在一起不会减少问题的信息量。或许你说它可以加强天平分辨能力，这就需要深入分析其作用。所以说直接套用信息量的做法，没有揭示其中的逻辑。好了，同分析简化问题看法一样，与其绕一圈套用信息的说法，不如考虑决策树来得直观。决策树【 1 】是这样的，天平在树的节点上，每个节点依天平的 3 种状态分出 3 个分支，称量的次数 k 相当于树的层数，决策树的叶子是几次称量后可以分辨的状态集。什么是问题空间的状态？每个球有两种状态“疑重”或“疑轻”，分别代表着它可能是重的次品和轻的次品，附上球的编号， n 个球对应着 2n 个状态。这些疑是次品球的状态通过通过节点，即天平称量的分流，沿着不同分支各自走向叶子。叶子中的状态是通过它所经路径称量的排除，次品和它的状态被确定到这里。如果要分辨出次品及其轻重，每个叶子只能包含一个状态，如果只要分辨出次品，叶子里包含的状态必须不超出一个球但可以包含这球的两个状态。举个具体例子。比如说 3 个球，按编号和“疑重”、“疑轻”， 6 种状态分别记为 1z 1q 2z 2q 3z 3q 。将 1 号和 2 号球分别放天平左边和右边， 3 号在外面，一次称量后的决策树如下：疑是次品球的状态及分配天平的状态称量后状态（ 1z 1q ） 3z 3q ——左重 1z 2q ——右重 1q 2z ——平衡 3z 3q 第一列表示称量前，所有疑是次品球的状态，及在天平的位置，园括号里的球在天平的左边，方括号的在右边，其他的在天平外边。第二列是称量时天平的状态。第三列是被称量后区分出的疑是次品球的状态集。比如说 1z 2q 是在天平左重时，疑是次品只可能是 1 号重或 2 号球轻。在这叶子里，因为有两个状态，有两个球号的还不知道次品是哪个。只有对应平衡时 3z 3q ，知道 3 号球是次品，但不知其轻重。细考决策树中，沿着所有平衡分支走到底的（全平衡）叶子，里面包含着每次称量都是平衡情况下的疑是次品球，它总是放在天平外。因为都没经过称量，所以它包含着每个球的两种状态。如果这叶子里只有一个球号，那个次品球就是它了，但不知其轻重。而所有其他叶子里的球，都至少经过了一次的称量，球一但上过天平，它的两种状态就分离开来，沿着两个分支走去，所以不可能同在一片叶子里。在这些叶子里，每个球都只能有一种状态。考虑 n 个球，通过称量要把它们区分出来，因为全平衡叶子必须包含一个球的两种状态，这需要 2n-1 片叶子。 K 次称量最多可以有 3**k 片叶子，我们有： 2n-1 = 3**k 即 n = （ 3**k+1 ） /2 。这是称 k 次能够区分球的上限。这个上限不一定能够达到，要看实际的测量是怎么分配的。下面的决策树是 13 球的一个区分方案：将 1-4 号球放天平左边， 5-8 号右边， 9-13 号外面，这里第 3 ， 5 ， 7 列是第一次、第二次、第三次称重后天平状态区分出疑是次品球的状态集，其中园括号里是下次称量时，天平左边中的球号状态；方括号则是右边的；括号外是在天平外待定的球号状态， x 表示在天平那边加一个正品球。称第一次状态及分配称第二次状态及分配称第三次状态 All States ——左重 (1z 2z 5q) 7q 8q ——左重 (1z) 6q ——左重 1z ——右重 2z ——平衡 6q ——右重 (3z) 5q ——左重 3z ——右重 4z ——平衡 5q ——平衡 (7q ) ——左重 8q ——右重 7q ——平衡 ——右重 (1q 2q 5z ) 7z 8z ——左重 (3q) 5z ——左重 4q ——右重 3q ——平衡 5z ——右重 (1q ) 6z ——左重 2q ——右重 1q ——平衡 6z ——平衡 (7z) ——左重 7z ——右重 8z ——平衡 ——平衡 (9z 9q 10z 10q) 12z 12q 13z 13q ——左重 (9z) 11q ——左重 9z ——右重 10z ——平衡 11q ——右重 (9q) 11z ——左重 10q ——右重 9q ——平衡 11z ——平衡 (12z 12q) 13z 13q ——左重 12z ——右重 12q ——平衡 13z 13q 这个决策树很直观地揭露出很多信息。其一，（ 3**k+1 ） /2 是个很好的上界，通过合适的配置可能实现。如在第一次平衡后的子树显示，加一个正品球就可以区分 5 个球达到了这个上界，注意到这个 13 球的决策树，叶子中有两个空位，如果称量时手里有个正品球，第一次称 9 个加上这个正品球， 3 次就能区分出 14 个球，也达到这个上界。所以 13 球的局限在于天平分配上，这暗示着没有已知正品球时，可以达到的极限是 n = （ 3**k-1 ） /2 。其二，因为全平衡叶子不能区分球的两种状态，如果要求确定次品的轻重，我们就不能利用这个叶子，所以这种情况下的极限是 n = （ 3**k-3 ） /2 。有了这些猜测和决策树分配的思路，不难用数学归纳法证明这些结论。在《称球问题》帖子里，有人建议用黄金分割法（优选法）来确定放在外面的球数，对 13 球这确实近似于正确值 5 ，但是 0.618 比率并没有与正确值有内在联系，也只是一个猜测法。从下面证明可以看出，对于称 k 次情况，放在外面的球数应该是（ 3**(k-1)+1 ） /2 。当 k 3 时，优选法建议的值就开始不对了。有人说，这题中的正品球应该是不可区分的，就像玻色子一样。这个改变了题意。不过探索新问题这也是做研究时常做的事，就像我们看到很漂亮的理论结果，就看看改变一下条件能否也得出有意义的结果。我想了一下，觉得这个改变把难度降低了点，家里有小孩的不妨让他们试试，这个（因为不可区分）不允许混合称过的球及没称过球的解法。问：在这时要几次才能分 13 球？反问题是：称 3 次可以从多少这样的球中找出次品？做研究、玩游戏和写帖子凡是有意义的，都需要有一点技术含量。这才对得起花时间的读者和自己的智商。有时看到没什么技术含量的东西却冠以夸张的说法，还顾盼自雄，真的很无语。这如果只是想炒作自己，尚无大害。如果做研究也是这般的态度，写的也是吹毛求疵但没有什么有意义的内容，类似于：发现了 Gale-Shapley 算法不符合“为稳定婚配设计的求偶规则”提法之类的口水文，为此洋洋自得，以为捍卫了数学的严谨性和科学的严肃性，那学生们就可堪忧虑了。【附录】称球问题通解的证明做研究最好的方法是先看简单特殊的问题，从直观中找出思路，经过前面这些思考，我们已经找到诀窍，所以不难将它扩大成一般性的结果。考虑一般问题，把球分三堆，放两堆等数的球上天平，如果平衡，次品当然在外面这一堆。如果不平衡，比如说左边重，我们只知道外边的肯定是正品，但次品不知道是在天平的哪一边。重的那一边的球定义为“疑重球”，如果在这边，那次品一定是较重。轻的那一边定义为“疑轻球”，若是在这边则次品较轻。所以天平上的这些球经过一次称量之后已经被消除掉一部分的不确定性，称为半确定的球。半确定的球集合中只有两类的球，疑重球或疑轻球，集合中可以混合着这两类球，但知道每个球属于哪一类。现在证明。在叙述时，我们只考虑这堆球的数量在可达到最多的情况。对少于这个数的情况，我们总是可以这样的安排：使得分三堆时，每一堆都不大于证明中分法的数量，这样归纳法总是能够进行下去。引理和定理中的球是可以达到的最大的数量，否则在三分时总有一方超过证明里分配的数量，从归纳法推导可以看出这将导致 k=1 情况下不可能实现。引理 1 ：在多于 2 个的一堆球，已知次品在其中，称 k 次可以并最多在 3**k 个半确定的球中找出次品，并且知道其轻重。用数学归纳法， k=1 。 3 个半确定的球，一定至少有两个属于同一类，比如说疑重球，将这两个上天平，重的那个就是次品，如果平衡，外边的那个就是次品，而且从它的类别知道这次品是较重还是较轻。验证正确。假设结论对 k-1 次正确。将不多于 3**k 个半确定的球三等分，如果不能够等分，除天平两边要等数外，三方都不多于 3**(k-1) 个球，且使得两边共有偶数个疑重球，记为 2a 个。这总是可以做到的。因为我们可以把天平上“不齐整”的球和外面异类的球对调。这样天平左右各有 a 个疑重球和 3**(k-1)-a 个疑轻球。这一般有多种可能的 a 值满足要求，任取一个都行。这时如果左边重，左边的 a 个疑重球和右边的 3**(k-1)-a 个疑轻球，共 3**(k-1) 个半确定球有嫌疑，其他都是正品。如果右边重，同理将嫌疑缩小到 3**(k-1) 个半确定球。如果平衡，嫌疑在外面的 3**(k-1) 个半确定球中。如果这嫌疑是 1 个或 2 个半确定球，可以用一个正品与其中一个称一次解决，其他情况我们已知用 k-1 次可以解决不多于 3**(k-1) 个半确定的球。证毕。引理 2 ：已知次品在其中，加一个已知的正品球称 k 次，可以并最多在（ 3**k+1 ） /2 个球中找出次品，但有且仅有一种情况不知其次品的轻重。在 k=1 情况，有 2 个球，取一个与正品球上天平，如果平衡，次品在外面，但不知它比正品轻还是重，注意这是归纳证明中仅有的情况。如果只有 1 个球，它就是次品了，称一次可以知道比正品轻了还是重。假设结论对 k-1 次正确。考虑第一次天平称量，一边取（ 3** （ k-1 ） -1 ） /2 个加上一个正品球，另一边取（ 3** （ k-1 ） +1 ） /2 个球。我们知道这次称量以后，如果天平平衡，那么嫌疑在外面。余下 k-1 次可以解决这里的不超过（ 3** （ k-1 ） +1 ） /2 个球，有且仅有一种情况不知其次品的轻重。如果天平不平衡，天平的两边都是半确定的球。由引理 1 知道，余下 k-1 次可以解决这里的 3**(k-1) 个球。因为这个数是奇数，所以我们必须在第一次天平称量时再加上一个已知的正品球。因此称 k 次，可以并最多解决 3** （ k-1 ） + （ 3** （ k-1 ） +1 ） /2= （ 3**k+1 ） /2 个球。证毕。定理：在一堆等重球中有一个重量不同的次品球，用天平称 k 次找出来，这堆球最多且可以是（ 3**k-1 ） /2 个球。在第一次称量我们最多可以将 3**(k-1)-1 个球两等分放在天平上，如果不平衡，由引理 1 ，可以再称 k-1 次解决。如果平衡，天平这里都是已知球，由引理 2 ，可以再称 k-1 次解决外面的（ 3** （ k-1 ） +1 ） /2 个球。所以总共可以解决（ 3**k-1 ） /2 个球。证毕。由这个定理我们可以知道称 2 ， 3 ， 4 ， 5 次，分别可以在 4 ， 13 ， 40 ， 121 个球中找出那个次品，因为这个证明是构造性的，所以知道该怎么称量。如果在称球问题中不知道有没有这个次品球存在，这和判别出嫌疑的次品球是较轻还是较重是同一个问题。在引理 2 证明中知道，只有每次分堆时，天平都是平衡的，总是被分在外面的那个球被认为是次品球时不知轻重。把这个球去掉，或者说要解决的问题少了一个球就行了。这也就是说，用天平称 k 次可以在一堆（ 3**k-3 ） /2 个球中确定有没有一个重量不同的次品，如果有，我们知道是哪一个，确定是较轻还是较重。有人问，如果我要解决问题那堆球比你构造性证明中的数量少，怎么办？你参考证明的提示，每次分堆时尽量三等分把不齐整的数搁在外边那堆，不就行了？【参考资料】【1】维基百科，决策树 http://zh.wikipedia.org/wiki/%E5%86%B3%E7%AD%96%E6%A0%91

个人分类: 智力|18596 次阅读|36 个评论

称球问题的两种方法

热度 8 Liweigang 2013-2-1 04:00

1 月 30 日，科学网的应行仁老师发表博文《称球问题》，提出智力思考堆栈( Call Stack) 的深度概念，获编辑部青睐，精选置顶。一时间科学网众博主兴趣多多，到目前为止共有 23 位博主推荐， 50 个评论， 3592 人次访问。称球问题的源头还是科普才女，张天蓉老师的杰作：有十三个球，其中十二个重量相同，只有一个次品，不知是轻了还是重了。请用天平秤三次，将这个次品找出来。本来应老师已给出基本的称法，大家深入理解就是了，但不想有两位较真的博主硬是要从命题本身来否定这个练脑小题。数学行家李世春老师看到后，以极大的兴趣另发博文《 8 个球就可以证明 “ 十三球问题 ” （称球问题）无解》，特别作出结论：无论怎么摆放球，称量 3 次不可能从 13 个球中找到那个次品。物理学家戴德昌老师也专门撰文，认为此问题需要穷举法和运气来解决，调侃道《称球问题是忽悠小朋友》，认为“哥哥”，的问题错了。本文给出高中生 Danilo Li ( 柱柱 ) 和巴西利亚大学博士生郑建亚对称球问题的的两种解法。 Danilo Li 的方法共列出 20 种可能通过 3 次秤球找到次品。郑建亚的的解法，共有 13 种可能称法找到次品。列出两种算法的目的在于说明称球问题应该有解，而且还有多种方法。本文应着张天蓉老师的初衷，让孩子和学生们练练脑。文中的表述仅以秤 3 次过程中相关的逻辑关系，找出次品为目的，没有任何完备性理论证明和数学模式化。期待着应行仁老师下一篇文章对此问题的构造性证明和新的提示。敬请应行仁老师、李世春老师和戴德昌老师等科学网的众博友指导访问。一、 Danilo Li 的解法 1. 四四分法的平衡情况第一次秤： A(4) 球 ――――――――――――― B( 4) 球 △ 上图中 A 表示天平的左边， B 表示天平的右边。括号内的数字表示天平该边托盘上放置的球的数目。 1.0: 两边平衡在 A 边保留 3 个球从剩余的 5 个球里面拿出 3 个放 B 边。平衡情况第二次秤： A(3) 球 ――――――――――――― B( 3) 球 △ 可分为两种情况： 1.1: 两边平衡在 A 边保留 1 个球，从剩余的 2 个球里面拿出 1 个放 B 边。第三次秤： A(1) 球 ――――――――――――― B( 1) 球 △ 1.1.1: 两边平衡从剩余的 1 个球是次品。 ( 第 1 种可能 ) 1.1.2: 两边不平衡 B 边的球是次品。 ( 第 2 种可能 ) 1.2: 两边不平衡 B 边的 3 个有次品 1.2.1 B 边朝下，说明次品更重 B 保留 1 个，从 B 边拿下的两个球任意一个放到 A 边第三次秤： A(1) 球 ――――――――――――― B( 1) 球 △ 三种情况： 1.2.1.1 A 边朝下，则是 A 边这个球是次品； ( 第 3 种可能 ) 1.2.1.2 B 边朝下，则是 B 边这个球是次品； ( 第 4 种可能 ) 1.2.1.3 两边平衡，则是原 B 边第 3 个球是次品。 ( 第 5 种可能 ) 2. 四四分法的不平衡情况由于该情况较复杂，下面在称球的过程中，加上各球的编号，分别放在天平两边托盘上面。第一次秤： 1,2,3,4 5,6,7,8 A(4) 球 ――――――――――――― B( 4) 球 △ 剩下 5 个球： 9 ， 10 ， 11 ， 12 ， 13 不平衡情况 - A 边朝下， B 边朝上情况 2.0: 两边不平衡因为第一次秤时的不平衡，次品应在 1 ， 2 ， 3 ， 4 号球或 5 ， 6 ， 7 ， 8 号球中。第二次秤： 1,2,5,6,7 9,10,11,12,13 A(5) 球 ――――――――――――― B( 5) 球 △ 将 B 边 3 个球： 5 ， 6 ， 7 号球放到 A 边。把原 A 边的球里拿出 2 个： 3 ， 4 号球。 2.1 两边平衡因为平衡，已知次品球在 3 ， 4 ，或 8 号球中。第三次秤： 3,8 9,10 A(2) 球 ――――――――――――― B( 2) 球 △ 2.1.1 两边平衡根据第二次秤时的平衡结果，在此情况下只有 4 号球是次品。 ( 第 6 种可能 ) 2.1.2 两边不平衡在此情况下 3 或 8 号球会是次品。 2.1.2.1 A 边朝下如果第一次秤， A 边朝下， 3 号球是次品。 ( 第 7 种可能 ) 如果第一次秤， B 边朝下， 8 号球是次品。 ( 第 8 种可能 ) 2.1.2.2 A 边朝上如果第一次秤， A 边朝下， 8 号球是次品。 ( 第 9 种可能 ) 如果第一次秤， B 边朝下， 3 号球是次品。 ( 第 10 种可能 ) 2.2 两边不平衡因为不平衡，已知次品球在 1 ， 2 ， 5 ， 6 或 7 号球之中。 2.2.1 第一次秤 A 边朝下且第二次秤 A 边还是朝下 1 或 2 号球会是次品。第三次秤： 1 2 A ( 1 ) 球 ――――――――――――― B ( 1 ) 球 △ 2.2.1.1 A 边朝下 1 号球是次品。 ( 第 11 种可能 ) 2.2.1.2 B 边朝下 2 号球是次品。 ( 第 12 种可能 ) 2.2.2 第一次秤 A 边朝下且第二次秤 A 边朝上 5 ， 6 或 7 号球是次品。第三次秤： 5 6 A(1) 球 ――――――――――――― B( 1) 球 △ 2.2.2.1 A 边朝下 6 号球是次品。 ( 第 13 种可能 ) 2.2.2.2 B 边朝下 5 号球是次品。 ( 第 14 种可能 ) 2.2.2.3 两边平衡 7 号球是次品。 ( 第 15 种可能 ) 2.2.3 第一次秤 A 边朝上且第二次秤 A 边朝下 5 ， 6 或 7 号球是次品。第三次秤： 5 6 A(1) 球 ――――――――――――― B( 1) 球 △ 2.2.3.1 A 边朝下 5 号球是次品。 ( 第 16 种可能 ) 2.2.3.2 B 边朝下 6 号球是次品。 ( 第 17 种可能 ) 2.2.3.3 两边平衡 7 号球是次品。 ( 第 18 种可能 ) 2.2.4 第一次秤 A 边朝上且第二次秤 A 边还是朝上第三次秤： 1 2 A(1) 球 ――――――――――――― B( 1) 球 △ 2.2.4.1 A 边朝下 2 号球是次品。 ( 第 19 种可能 ) 2.2.4.2 B 边朝下 1 号球是次品。 ( 第 20 种可能 ) 二、郑建亚的解法该算法也是基于四四分法，将 13 个球分别进行编号， 1-13 号。 ?为标准球。第一步（ 1 ， 2 ， 3 ， 4 ） VS （ 5 ， 6 ， 7 ， 8 ）共有两种情况：平衡 1.1 和不平衡 1.2 1.1 天平平衡，说明问题在（ 9 ， 10 ， 11 ， 12 ， 13 ），其他球为标准球。第二步（ 9 ， 10 ， 11 ） VS （ ?，?，? ）同样有两种情况：平衡 1.1.1 和不平衡 1.1.2 1.1.1 平衡说明问题在（ 12 ， 13 ）球。第三步：（ 12 ） VS （ ? ）得到结果：如果平衡， 13 号是次球。如果不平衡， 12 是次球。 1.1.2 不平衡说明问题在（ 9 ， 10 ， 11 ）球，而且知道次球比标准球是轻还是重。第三步：（ 9 ） VS （ 10 ）得到结果：如果平衡， 11 号是次球。如果不平衡，根据次球的轻重可以确定 10 或 9 哪个是次球。 1.2 天平不平衡，说明问题在（ 1 ， 2 ， 3 ， 4 ， 5 ， 6 ， 7 ， 8 ）球。同时可知重量（ 1+2+3+4 或 5+6+7+8 ）第二步（ 1 ， 2 ， 3 ， 5 ） VS （ 4 ， ?，?，? ）有两种情况： 1.2.1 平衡和 1.2.2 不平衡。 1.2.1 平衡说明问题在（ 6 ， 7 ， 8 ）球。而且可以确定次球轻重。第三步（ 6 ） VS （ 7 ）得到结果：如果平衡， 8 号是次球。如果不平衡，根据次球轻重可知 7 或 6 号是次球。 1.2.2 如果不平衡说明问题在（ 1 ， 2 ， 3 ， 4 ， 5 ）球。不平衡有两种情况， 1.2.2.1 天平倾斜不变， 1.2.2.2 天平倾斜改变。 1.2.2.1 天平倾斜改变，说明问题出在（ 4 ， 5 ）球。第三步（ 4 ） vs （ ? ）得到结果：如果平衡， 5 号是次球。如果不平衡， 4 号是次球。 1.2.2.2 天平倾斜不变，说明问题出在（ 1 ， 2 ， 3 ）球。且可知次球轻重。第三步（ 1 ） vs （ 2 ）得到结果：如果平衡， 3 号是次球。如果不平衡，根据次球轻重可知 2 或 1 号是次球。感谢以上提到的各位老师和科学网的众博主的支持和关注。注：应行仁老师已给出该问题的通解，请见： http://blog.sciencenet.cn/blog-826653-658533.html

个人分类: 社交网络|10452 次阅读|29 个评论

8个球就可以证明“十三球问题”（称球问题）无【？】解

热度 11 大毛忽洞 2013-1-30 21:13

8 个球就可以证明“十三球问题”无【？】解 " 有十三个球，其中十二个重量相同，只有一个次品不知是轻还是重了。请用天平称三次，将这个次品找出来。 " http://blog.sciencenet.cn/blog-826653-657778.html 【博主后记】应老师的命题是正确的，俺的推理有问题。注意，原来的【1】到【6】的推理都没有错误。只是在讨论【13球】时，出了问题。为了纪念，俺在博文的题目加了个【？】。数学问题，第一要求应该是严谨。严谨到毫无讨价还价的余地。 13 个球，只有 1 个次品。次品定义：不知道这个次品是轻了还是重了。这就得到一个推论：在 2 个球中，如果有 1 个是次品，用天平无法判断出次品。 “称三次”，不能超过 3 次使用天平。在这样的数学前提下，“十三球问题”（称球问题）无【？】解。【 1 】 2 个球（ A 球和 B 球）如果只有两球，其中有一个次品，不知道是轻了还是重了，天平能确定出次品吗？不能。 A 球――――――――――――― B 球 △ A 和 B 失衡，因为不知道次品是轻了还是重了，因此无法判断出谁是次品！【 2 】 3 个球（ A 球、 B 球和 C 球） A 球――――――――――――― B 球 △ 如果 A 和 B 平衡，证明 A 和 B 是正品，则可判断出次品就是 C 。如果 A 和 B 失衡，证明次品就在 A 和 B 中，需要再称一次才能判断出是 A 还是 B 。结论： 3 个球需要称 2 次。【 3 】 4 个球（ A 球、 B 球、 C 球和 D 球）情况 1 ： A 球――――――――――――― B 球 △ 如果 A 和 B 平衡，证明 A 和 B 合格，次品是 C 或 D 。再称一次就可以判断出 C 和 D 谁是次品。情况 2 ： A 球――――――――――――― B 球 △ 如果 A 和 B 失衡，证明次品就是 A 或 B ，由此可判断出 C 和 D 是正品。需要再称一次，才能判断出 A 和 B 谁是次品。结论： 4 个球需要称 2 次。【 4 】 5 个球（ A 球、 B 球、 C 球、 D 球和 E 球）情况 1 ： A 球――――――――――――― B 球 △ 如果 A 和 B 平衡，证明 A 和 B 是正品，则可判断出次品在 C 、 D 、 E 中。 C 、 D 、 E 三个球中有次品，这正是“ 3 球问题”，仍需要称 2 次才能判断出次品。因此，这种情况需要称 3 次才能判断。情况 2 ： A 球――――――――――――― B 球 △ 如果 A 和 B 失衡，证明次品就在 A 和 B 中。需要再称 1 次就可以判断。结论： 5 个球需要称 3 次。【 4 】 6 个球（ A 球、 B 球、 C 球、 D 球、 E 球和 F 球）情况 1 ： A 球――――――――――――― B 球 △ 如果 A 和 B 平衡，证明 A 和 B 合格，则可以判断出次品在 C 、 D 、 E 、 F 中，这就使问题归纳为“ 4 球问题”，需要再称 2 次才能判断。情况 2 ： A 球――――――――――――― B 球 △ 如果 A 和 B 失衡，证明次品就在 A 和 B ，再称 1 次就可以判断 A 和 B 谁是次品。结论： 6 个球需要称 3 次。【 5 】 7 个球（ A 球、 B 球、 C 球、 D 球、 E 球、 F 球和 G 球）情况 1 ： AB 球――――――――――――― CD 球 △ 如果两边平衡，证明这 4 个球是正品，则可以判断次品在 E 、 F 、 G 中，这就使问题归纳为“ 3 球问题”，需要再称 2 次才能判断。情况 2 ： AB 球――――――――――――― CD 球 △ 如果两边失衡，证明次品就在 ABCD 中，这就把问题归纳为“ 4 球问题”，需要再称 2 次才能判断出次品。结论： 7 个球需要称 3 次。【 6 】 8 个球（ A 球、 B 球、 C 球、 D 球、 E 球、 F 球、 G 球和 I 球）情况 1 ： AB 球――――――――――――― CD 球 △ 如果两边平衡，证明这 4 个球是正品，则可以判断次品在 E 、 F 、 G 、 I 中，这就使问题归纳为“ 4 球问题”，需要再称 2 次才能判断。情况 2 ： AB 球――――――――――――― CD 球 △ 如果两边失衡，证明次品就在 ABCD 中，这就把问题归纳为“ 4 球问题”，需要再称 2 次才能判断出次品。结论： 8 个球需要称 3 次。关于“ 13 个球问题”： " 有十三个球，其中十二个重量相同，只有一个次品不知是轻还是重了。请用天平称三次，将这个次品找出来。 " 情况 1 ： 4 个球――――――――――――― 4 个球 △ 如果以上这 8 个球平衡，证明次品就在剩下的那 5 个球中。在 5 个球中找到次品需要称2 次，因为有1个正品来对比。情况 2 ： 4 个球――――――――――――― 4 个球 △ 如果以上这 8 个球失衡衡，证明次品就在这 8 个球中。【后记】：如果失衡，第一个天平可以给出一个表达式，结合这个表达式，可以解决在 8 个球中找到次品的问题，只需要2次。结论： 4+4+5摆放球，称量 3 次可能从 13 个球中找到哪个次品。谢谢网友的批评指正。【最后记】：幸亏俺是老老实实地讨论问题，没有使用感情动词。

个人分类: 闲情和逸致|13532 次阅读|45 个评论

帐号		自动登录	找回密码
密码			注册

关闭安全验证

标签: 称球问题

相关帖子

相关日志

关闭 安全验证

标签: 称球问题

相关帖子

相关日志

关闭安全验证