12 枚金币中有 1 枚是假的,用天平称 3 次找出结果。

2 分

6,3,1

每次等分三份，称其中两份

@hinate @vietor 这个只是找出假金币，但是没有找出假金币比正常金币轻了还是重了
@zhjits 这个好像也找不出轻重的。

在不知道轻还是重的情况下 2 分不能解决...因为第一次称好了完全不知道到底哪个是标准的...
所以至少也得是 3 分....

@ncdx2009 为什么会找不出轻重？

@sorcerer 哦有次数规定

3 分吧

这题很有趣，小学的时候我爸喜欢给我出这种益智题，当时拿到这道题真的没头绪，晚上睡觉后闭上眼想了半个小时想出来激动得...

给几个提示：
1.给每个硬币编号。
2.硬币间可以交换位置，看天平重轻方向是否改变。
3.原题关键字是“ 12 个乒乓球特征相同 其中只有一个重量异常”搜一搜就有答案了。

一个天平可以比较三份数目相等的硬币，楼主按照这个思路就行

很经典的题目，从小学做到工作。关键的一步就是在第二次测量时要重新分组

这个之前看过，我说详细点好了，假设硬币叫做 1-12 ：
a. 分 3 份，分别是 1-4 ， 5-8 ， 9-12 ，称 1-4 和 9-8 ，平的话就在 9-12 ，没啥好说的。
b.假设 1 ， 2 ， 3 ， 4 轻， 5 ， 6 ， 7 ， 8 重，那么确定 9 ， 10 ， 11 ， 12 是真的硬币。
c.拿出 1 和 3 个 9-12 里面的，比如 1 ， 9 ， 10 ， 11 ，这里面只有 1 需要确定是不是假的。
d.拿出 1 ， 9 ， 10 ， 11 和 2 ， 3 ， 4 ， 5 称，如果平的话就是 6 ， 7 ， 8 有问题，不用说了。

e.如果 1 ， 9 ， 10 ， 11 轻，那么 1 ， 5 有问题，因为 6 ， 7 ， 8 已经知道没问题， 2 ， 3 ， 4 有问题的话现在 2 ， 3 ， 4 从左边换到了右边，右边应该轻才对， 1 ， 5 有问题的话把 1 和一个真币称一下就知道谁是假币了。

f.如果 1 ， 9 ， 10 ， 11 重，那么 2 ， 3 ， 4 有问题，因为 1 ， 5 有问题的话 1 ， 5 都没有换边，轻重不会变，其实就是 2 ， 3 ， 4 换了位置导致轻重关系变了，到这步的话确定假币是偏轻的。 2 ， 3 ， 4 里面， 2 和 3 称一下轻的是假的，平的话 4 是假的。

信息论的题，刚学
称重可能得到三种结果:一边轻、一边重、两边平衡
H_1(x)=log(2)(3)
一共有 N 个球，假球可能轻可能重， N*2
H_2(x)=log(2)(2N)
需要最少次数在( H_1(x)/H_2(x) , H_1(x)/H_2(x)+1 )之间取整数
120 个球即 N=120
H_1(x)/H_2(x)=4.98869 ……
所以 5 次肯定可以
LaTeX 不熟，不会写对数，公式都是以 2 为底，将就看吧

@amet 计算次数时分子分母写反了 ……

6/6 ， 3/3 ， 1/1 (1-1-1 排除法)

幼儿园水平水平

金田一做过这个题目……

@amet 按照你这里的理论， 3 次应该可以分 13 个球（ 3^3 > 13*2 ），然而我见到的题目全是 12 ，我相信不是出题者和做题者没有想到 13 的解法。事实上你不能保证每次获得的信息都是最好的（或者说是对于各种情况都是比较平均的），比如可能在某一步一边重留下的情况比较多，一样重留下的情况比较少。

@mfinal 我问过不少人这个题目，一半的人脱口而出“二分法”、“真简单”，说明都太自信了。

只针对这道题的话 第一次看见是在这里 http://blog.csdn.net/pongba/archive/2008/06/13/2544933.aspx

https://en.wikipedia.org/wiki/Balance_puzzle
https://zh.wikipedia.org/wiki/%E7%A8%B1%E7%90%83%E5%95%8F%E9%A1%8C

我记得这是以前初中的智力题, 不难的, 我家那个小弟弟认真想想就可以解出来

这一题不是考智商的，这是一个记忆题，因为这个题目已经烂大街了…

@Xs0ul
13 和 12 真的没区别吧
一样解法

@ncdx2009 金的密度高，所以假的肯定轻

@pimin 13 称 3 次，好像真的解决不了，操作上不能实现。类似简单的 4 枚称 2 次，信息论上可行，操作上不能实现。

@vietor ，金币中含金量是有限的，不能排除使用含金量高的“假金币”来走私黄金

@pimin 称球问题是指若在最多 (3^n-3)/2 个球中有一个特殊球的重量与众不同（不知道偏重还是偏轻），而其他球的重量全部相同，则用无砝码的天平称 n 次可以找出特殊球，并确定特殊球是偏轻还是偏重；如果有 (3^n-1)/2 个球，则同样可以保证找出特殊球，但不一定能确定特殊球是偏轻还是偏重
来自维基百科 https://zh.wikipedia.org/wiki/%E7%A8%B1%E7%90%83%E5%95%8F%E9%A1%8C

@ncdx2009 楼主可以看看维基百科提到的矩阵解法

@Xs0ul 目前是按照这个矩阵解法进行的编程练习, 这解法的数量增长太快了,12 枚称 3 次是 2 的 12 次方(4 位数) , 到 120 枚称 5 次是 2 的 120 次方(37 位数) 。

12 个球有 1 个异常。可能性有 24 种。称相当于 3 进制。所以 3 位的编码就够了。理论上 13 个球应该也行啊。求大神来个 13 球版的

这不是很简单吗，二进制编码原理

@amet @kaizixyz 正解，信息论的题，天平有三种状态，假球有 2N 种状态，只要 3^m > 2N 就一定能求解

@amet 信息论只能给出下界，如果有两个是假的，那好像是找不出实际方案来达到信息论下界的上取整的