您还未登陆，请登录后操作！
有一次品，重量比正品轻，有一台无法抹天平，如何找出次品
您的举报已经提交成功，我们将尽快处理，谢谢！
先各自40个分2边放看那个低，低的那40个中有次品，再依次将40分2批这样去比较下去就可以了，如果我的答案对你有用麻烦点击“好评”，谢谢！
大家还关注有一堆乒乓球，其中有一个较重的是次品，用天平称2次可以把这个次品找出来，最多是多少最小是多少
有一堆乒乓球，其中有一个较重的是次品，用天平称2次可以把这个次品找出来，最多是多少最小是多少
满意回答2次能找出来，说明这个数据大于3的一次方而小于4或等于3的二次方，即最小是4，最大是9N 个乒乓球中有一个和其他的质量不同，用天平最少几次一定能称出来？
注：原题描述中n为999很有趣的一道题？！知友们，问的是“最少”啊！
按投票排序
答案是七次。 给的文献是靠谱的，只是没有给出具体操作，具体操作在文献的参考里。The Problem of the Pennies, F. J. Dyson, The Mathematical Gazette , Vol. 30, No. 291 (Oct., 1946), pp. 231-234我现在把具体操作写出来：最重要的一步是给球编码。我们取所有 7 位三进制数，共有个编码，去掉所有位数都一样的情况，共有个编码。其中有一半，首次出现邻位不同的情况是 01, 12 或 20，这样的编码叫「正序」的，否则是「逆序」的。正序码共个。把一个正序码中的 1 换成 2，2 换成 0，0 换成 1，结果仍然是正序的。我们把可以通过这种方式相互转换的三个码作为一组。现在把正序码一组一组的分配给乒乓球。因为此题中是 999 个球，正好分完 333 组，没有不完整的组。否则还要调整。对每一个球，将其正序码中的 0 和 2 对换，得到相应的逆序码。因此每个球有两套编码。接下来称球。在第 k 次称球中，将正序码第 k 位为 0 的 333 个球放在天平左边，正序码第 k 位为 2 的 333 个放在右边，其他球放在旁边。如果左边重，记 0。如果右边重，记 2。如果平衡，记 1。这样我们得到一个 7 位三进制码。这个三进制码编号的球就是与众不同的球，如果该码是正序的，该球较重；如果逆序，该球较轻。下面以 6 个球举例。取 3 位三进制正序码，共 12 个。取其中两组 (010, 121, 202) 和 (012, 201, 120)，依次分配给六个球。第一次称 010, 012 - 202, 201第二次称 202, 201 - 121, 120第三次称 010, 120 - 202, 012结果举例：012 说明第四个球比较重，021 说明第五个球比较轻。加一个 12 球的例子，见这个网页（英语）补充：几个新答案做出 2 次最多称 4 个，3 次最多称 13 个这样的归纳。如果需要知道次品的轻重，n 次最多称 (3^n-3)/2 个球。4 个球必须称 3 次才能确定找出坏球，并知道轻重。我开头引用的文献严格证明了这是最优的，多于 (3^n-3)/2 无解。如果不关心轻重，n 次最多的确可以称 (3^n-1)/2 个球，将多出的那个编号为 111...11 即可。下载文献可能不方便，我把证明截图贴在下面。
楼上给的具体实现方法基本已经很清楚了。这里从信息量角度解释一下原因以及称量次数的一般计算方法。为什么999个球是7次？12个球是3次？为什么6个球还是3次？？？每一次称量，带来的结果有3种，左边重，右边重，一样重，给我们带来的信息量是 大约是1.58 bit 的样子。999个球有一个球重量不一样，那么总共可能有 999*2 种结果（1号球轻，1号球重，2号球轻，2号球重......999号球轻，999号球重）。判断出结果需要的信息量是 大约是10.96 bit。所以需要的次数就是10.96/1.58 大约是6.94，向上取整需要7次。12个球需要的次数就是 大约是2.89，向上取整为3次。6个球还是3次，为毛？因为 大约是2.26，所以取整了还是3次。这个东西除了估算需要的次数有什么用呢？答案是没有什么用，而且有时候可能还会因为一些问题引起误差。比如说按这种方法计算的次数，4个球两次就能称出来。先试着想一下，你会发现想破脑袋也想不出来。怎么称呢？1.33个球放左边，1.33个放右边，剩下1.33个不称。1.33个球要怎么放在天平上？？？这怎么玩儿？所以4个球称两次称出来，这是没有可操作性的。“哥只告诉你们这种方法一定存在，你们慢慢去找，找得到是哥的水平高，找不到是你们太蠢。”
——克劳德·艾尔伍德·香农开始成为坚定的信息论黑香农黑了吧？所以说没有学过信息论的人和学过信息论的人怎么可能在一起？————————————————这里是日的分割线首先说一下什么叫香农定理是存在性定理，就是香农定理会指出最理想化的编码算法能达到的位数底线，就是这样的理想算法理论上存在，但是这种理想的算法不一定能在现实中被发现或实现。我写这个答案的初衷是单纯从信息论的角度上来看待一下这个问题，换句话就是给出可能的理想情况编码位数下限，而前面 的答案则是一种现成的算法。这个算法美不美？很美，三进制的思路可能是借鉴前人的，但是利用正向序列映射，通过天平的结果记录直观得出哪个球轻了还是重了，非常巧妙。（P.S.可以去看下那个给1000只老鼠喝毒药的问题，就是这个映射的二进制版本，因为天平有三种情况，“左偏”“右偏”“平”，老鼠只有“死”“活”）这可能是人类可以找出的最完美的算法了，但是这是理想的算法吗？不是。为什么？理想情况下的三次称量结果带来的信息量是,而这里呢？。因为三次称量“全是大于”，“全是小于”，“全是等于”的情况在这种算法里是不可能出现的。这就是不完美的地方，单从天平而言，这三种情况本来可以带给我们信息量，但是由于算法设计不可能出现，就降低了天平能传达的信息量。一句题外话，这也就是为什么12个球3次的情况在这里显得这么完美。因为12个球的每个可能有轻重，这个信息量是多少？！刚好是这种算法称三次的理想情况。讨论一下完美的情况有什么要求。信源熵是应该没疑问了，N代表球数。次数 m=/ 的条件是，每次称量的信息量都为，也就是每次称量的结果都要是独立且出现概率均为1/3。这也就是为什么4个球两次不能出轻重，具体计算难度不高篇幅太大打公式太麻烦，但是是无法在每次称量中得到的信息量。怎么样才能做到每次称量得到？整数个的球是没办法做到的。但是如果你允许我放0.5个球，或者0.33个球在天平上呢？每个球切两半，4个记为AA BB CC DD。先称AB CC，AB=CC，必为D异常，随便拿个ABC跟D称一下好了。AB&CC，D一定正常，A或B轻，或C重，称AA BD： AA&BD A-
AA&BD B-AB&CC, D一定正常，A或B重，或C轻，称AA BD：AA&BD B+
AA&BD A+这里其实已经有偷换概念在里面了，这个问题的信息量计算起来麻烦一些（粗看了下结果好像没错，不过要是错了就掉大了！！！）但是我想体现的是，这种看起来很完美的算法，也是受到了整数的局限。最后是吐槽部分：你们都以为我是信息论吹么？我是信息论黑啊！问题可以讨论不出来立场必须摆正啊！这也就是说的信息论各大定理的存在性，完美的算法不一定等于理想的情况，理想的情况不一定取得到，就是这样。至于怎么搞完美算法？别找我，我只负责算理想情况。所以说信息论有啥用呢？过去听过一个笑话，养鸡场的鸡蛋老是被压碎，找了一群物理学家研究，他们得出了一个完美的解决方案，但是只对真空中的球形鸡蛋有效。以上。
的文献和 的解析太赞了，集精巧和严谨于一身，可以说小球称重问题已经得到了圆满的解决。为了更直观、更易懂、让PDF恐惧症患者都能弄明白，我做了个小程序来演示，。支持3~999个球；用户自行选择哪个球是特殊球，是轻还是重，然后由电脑自动分组称量；用绿色代表轻，红色代表重；演示界面大致是这么个效果：希望能帮助大家更好地理解。PS：知乎要是能嵌入代码我就不至于把它放到单独的网站上了，不过这大概不太可能……
7次（感谢洪涛的提醒，我算错了两次....)虽然我赞同了
的答案，但是我依然想要占据一个答案位为什么这么做，因为洪涛答案中推荐的文章非常的值得一读，因为那个文章普及了信息论的基础知识所以我这个答案出现的原因是想要再推荐一下洪涛答案中的文章但是还是很多人有pdf恐惧症，那么如果有pdf恐惧症的话，那么就看这两个文章吧PS: 所有讲快排的时候不讲解空间的都是耍流氓.......
7次用文章末最後的結論（第八節）update＝＝＝＝＝＝＝這篇文章出自數學傳播這本雜誌，只給出了理論上的下界，沒有給出具體的方法，雜誌由台灣主辦在網上可以免費閱讀。一個更具體的例子是12個球，大部分人的方法要稱4次，這篇文章中通過編碼的方法，只用了三次更一般的方法見陳浩的答案。用這個方法理論上的下界總是可以達到的，應投稿給，我想他會很喜歎。
楼上说的很多的解法，看着挺绕的。发现一个用矩阵的方式求解的一个解法。貌似容易懂很多。看到那个矩阵的时候，瞬间就可以明白了。
根据信息论来解
7次是正确的，
说的非常清楚了，这里给PDF恐惧症患者做一下补充说明，不太严谨，不过比较直观。题目中999个球中含有一个特殊的球，一共有（999 * 2 =）1998种不同的情况（每个球都可能特殊*轻或重两种可能），而天平每次称量存在左边轻、右边轻、两边一样三种可能。我们唯一能做的，就是通过称量可以排除称量结果矛盾的情况（比方说左边放球0~332,右边放333~665，666~998不放，左边轻可以排除0~332中有个球重、333~665有个球轻，666~998存在特殊球共（333 + 333 + 666 =）1332种情况，还剩余（1998 - 1332 = ）666种情况待确定），一直排除到仅剩1个（某个球轻/重）或2个（某个球特殊，轻重未定，如果题目作进一步要求，那么极端情况还要多称量一次），既然要保证一定有解，我们假定每次称量的结果都是对我们最坏的，也就是排除情况最少的，那么我们就要尽可能的平均分配天平每个结果蕴含的情况，基本上每次可以排除掉原来的2/3，如果能够找到这样的分配方法，我们就可以断定n次称量最多在约3^n个球中找到一个特殊球（由于存在剩余情况总数并非3的倍数的时刻，有时剩余的可能性略多于原来的1/3）。至于具体的操作实现，需要利用一个很妙的事实：第一次均分之后至少有1/3的球可确认做标准球，用于辅助以后的称量（如果每次称量之后就把没问题的球扔在一边，次数是无法保障的呦~），从可能的情况而非球的个数考虑，才能得到正确的解。————————————————————————————————这个问题不是开放性问题，也已经有了几个优秀的解答，为什么还是不断重复出现错误答案？
@张恒 同学，注意楼主说的是＂一定＂能称出来，你的情况属于偶然，并不一定。先分ABC份，一份333个，称AB，AB平衡，则说明不同质量的在C中；不平衡，要注意了：再称一次AC。1、A两次都往下，说明不同质量的在A中，且质量较重；同理都往上，说明质量较轻2、AC平衡，说明不同质量的在B中，且B往下，质量重，B往上，质量轻因为要＂一定＂，我们就得按次数多的算，两次了。接下去就简单了，继续三分，（假设质量不同的是较轻的）三、每份111个四、每份37个五、每份13个六、每份五个七、每份两个八、每份一个所以，应该是八次。
不知道题中「一次」是如何定义的，如果是「不把之前的球拿下来」的话，两次就够了。1.一个一个的将球同时放到两边的托盘中，如果一次，托盘不能平衡了，则其必然在刚刚加入托盘了两个球之中。2.取出刚才放入的两个球，再随便拿一个球出来，与两个球中的一个对比，若质量不同，则就是它，若相同，则是另一个。
额。。。题主，你确定是“最少”，我怎么觉得最少一次就算出来了？和同学想的一样。一共999个，那么先左右都放499个，如果足够幸运，会发现此时天平持平那剩下没放上去的那一个...不就是质量不对的那个吗？
1、分成 a b c 三份 每份 333 个 称a b
如果相同 不同的那个肯定在c里 称重 共称1次2、将c 重新分成 abc 三份 每份 111 个 和第一步一样称重
称重1次 共称2次3、 重新分 每份37 个 称重1次
共称3次4、 重新分 每份12个 称重2次 共5次
如果三份重量相同 质量不同的就是 剩下的那一个 共称5次
否则 第五步5、 将找出的12个分三份 每份四个 称重1次 共6次6、 将最后剩下的4个拿出三个 和第4步相同的方法称2次 共8ci-------------------------------------------------------------------------------------------------以上的结论是最少5次
可。。。。。如果你敢想象第4步的运气那为什么不直接拿出一个说就这个和其它不同。。。。称重0次 如果没人反对 你赢了 共称0次 概率 1/999但是这不科学 所以我们拿三个 称两次 概率1/333
有一种解法是用信息熵来解答的
999个球，其共有W=1998种可能，其信息熵为
S=log W /log 2
称重有三种结果，大于，小于，等于，每次可获得的最大信息熵为
S=1.58 bit
然后假定每次操作均可获得最大信息熵 则需要操作
10.97/1.58=6.9=7次
——在物理书上剽窃来的
（每份333个）
（每份111个）
（每份37个）
37个4次（15 15 7 运气差）
15个5次 （7 7 1 运气差）
（3 3 1 运气差）
（1 1 1 必定出）
我记得这是一个有关信息论的问题，每称一次可以获得3的信息量，称n次信息量为3^n，由于不知道轻重之分，只要这个值大于999的2倍就可以了吧
分两种情况：1、取出一个球，剩下分成两堆，将这两堆放天平两端，但是，注意，放球的方法不一样：分别在两边一个球一个球的放，放到天平不平衡的时候，将刚放的那个球挑出来与还未放的球挑一个出来称就知道哪个球有问题，而且是轻还是重了，这样就需要称两次；如果运气不好，球都放完了还平衡，那就是999中挑出来的那个有问题，再称一次就知道是轻还是重了，故也需要两次。这种方法比较耗时，需要一个一个的放球，还需要等天平平衡。2、如果不允许一个一个的放球，将分出来的球全部装进袋子中一下子称重，那方法就是很多知友提到的7次，不再赘述。从现实角度考量，如果有人真的要去找这个球，应该会用第二种方法，因为时间关系。试想，让你去在999个球中找这个不知是重还是轻的球，你会一个一个称，然后慢慢等天平平衡吗？肯定是一下子挑一堆放在天平上，故正解应该是7次的第二种方法。
333称333，有轻重就111轻111重称111重111轻，以此类推，有轻重再称1次-2/3数目不够可以填平的，例如18轻18重称9轻9重18平，最多是（3的N次方-1）/2，可以知道轻重，例如13个，是4称4，平是2平+1称3个，3（重或轻）。1称1知轻重，如果左4重右4轻，2轻2重称1轻2平是2重1轻有问题，左轻是2轻有问题，左重是2重1轻有问题，在称2个的就知道轻重
从信息论的角度来看的话，用天平称重一次，我们能得到1比特的信息。所以理论上来讲要找出1000个球中的一个，至少需要称10次(2^10=1024)。也就是说理论上至少需要称10次。
为嘛我算错了有一队乒乓球,其中有一个较轻的是次品.用天平称至少称7次能找出这个较轻的乒乓球,这堆乒乓球可能是多少个?_百度作业帮
拍照搜题，秒出答案
有一队乒乓球,其中有一个较轻的是次品.用天平称至少称7次能找出这个较轻的乒乓球,这堆乒乓球可能是多少个?
有一队乒乓球,其中有一个较轻的是次品.用天平称至少称7次能找出这个较轻的乒乓球,这堆乒乓球可能是多少个?
3个一次；9个2次；27个3次；81个4次；243个5次.
您可能关注的推广回答者：36个乒乓球中有一个次品,它比正品轻一些.用一个没有砝码的天平至少称多少次,就能保证把这个次品找出来急啊~~~尽快!_百度作业帮
拍照搜题，秒出答案
36个乒乓球中有一个次品,它比正品轻一些.用一个没有砝码的天平至少称多少次,就能保证把这个次品找出来急啊~~~尽快!
36个乒乓球中有一个次品,它比正品轻一些.用一个没有砝码的天平至少称多少次,就能保证把这个次品找出来急啊~~~尽快!
至少要3次,最多要五次.可以把36个分成两份,一边18,轻的一边有次品,再把它们分成9个一份,轻的一边有次品,然后把轻的再分成4 4 1,如果两组4个的一样重,则另一个就是次品,如果不是则至多再用同样方法两次就可找出次品
您可能关注的推广回答者：