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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3163 天前的主题，其中的信息可能已经有所发展或是发生改变。

12 枚金币外观相同，正常金币重量是标准一致的，假金币只是重量异常，天平没有砝码，如何只称 3 次，找出假金币以及它比正常金币轻了还是重了。
这个问题，网上随便一搜就能找到答案，只是金币换成了小球或别的什么。
有没有用编程作一个通用的解决办法？例如 120 枚中 1 枚假的，称 5 次能不能找出假金币的轻重等
试着用穷举法做了一个，发现计算量有点大。
求思路或答案。

第 1 条附言 · 2016-04-04 14:49:18 +08:00

还是写个答案吧，有些人不认真读题了。。。
这种格式的答案，楼主穷举了一下，有 304 个，大致就是按照按照 21 楼链接中的方法——矩阵乘法。但这个按照算法，称 5 次时，数量已经大了很多，现在还没算出来 120 枚称 5 次时的答案。楼主更感兴趣的怎么用编程方法，解决这来问题。

一 01, 02, 03, 04 09, 10, 11, 12
二 01, 05, 06, 09 03, 04, 08, 12
三 02, 05, 07, 10 01, 04, 06, 09
结果清单如下
L,O,R 分别表示天平的结果:左重,平衡,右重，
L L R 01 重
L O L 02 重
L R O 03 重
L R R 04 重
O L L 05 重
O L R 06 重
O O L 07 重
O R O 08 重
R L R 09 重
R O L 10 重
R O O 11 重
R R O 12 重
O O O 无
R R L 01 轻
R O R 02 轻
R L O 03 轻
R L L 04 轻
O R R 05 轻
O R L 06 轻
O O R 07 轻
O L O 08 轻
L R L 09 轻
L O R 10 轻
L O O 11 轻
L L O 12 轻

金币

天平

穷举法

重量

32 条回复 • 2016-04-05 23:30:58 +08:00

hinate

2016-04-04 12:25:34 +08:00

2 分

vietor

2016-04-04 12:25:45 +08:00 via Android

6,3,1

zhjits

2016-04-04 12:28:55 +08:00

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

ncdx2009

2016-04-04 12:33:42 +08:00

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

smallfount

2016-04-04 12:34:58 +08:00

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

sorcerer

2016-04-04 12:36:19 +08:00 via iPhone

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

sorcerer

2016-04-04 12:37:10 +08:00 via iPhone

@sorcerer 哦有次数规定

Fleeting

2016-04-04 12:37:13 +08:00 via Android

3 分吧

sciooga

2016-04-04 12:55:33 +08:00

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

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

srlp

2016-04-04 12:56:39 +08:00

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

233

2016-04-04 12:57:55 +08:00

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

allan888

2016-04-04 13:17:36 +08:00

这个之前看过，我说详细点好了，假设硬币叫做 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 是假的。

amet

2016-04-04 13:34:10 +08:00

信息论的题，刚学
称重可能得到三种结果:一边轻、一边重、两边平衡
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

2016-04-04 13:38:16 +08:00

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

sigone

2016-04-04 13:46:08 +08:00 via Android

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

幼儿园水平水平

steveshi

2016-04-04 13:48:40 +08:00

金田一做过这个题目……

Xs0ul

2016-04-04 14:00:30 +08:00

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

mfinal

2016-04-04 14:07:41 +08:00

@sigone 强调了不知道有问题是轻 or 重🙈，不仔细看题也看看前面的评论吧..

Exin

2016-04-04 14:15:14 +08:00

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

mimzy

2016-04-04 14:22:24 +08:00 via Android

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

luguozmy

2016-04-04 14:27:32 +08:00

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

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

loading

2016-04-04 14:28:07 +08:00 via Android

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

pimin

2016-04-04 14:50:57 +08:00 via Android

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

vietor

2016-04-04 14:51:02 +08:00 via Android

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

ncdx2009

2016-04-04 15:03:51 +08:00

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

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

Xs0ul

2016-04-04 15:04:09 +08:00

@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 楼主可以看看维基百科提到的矩阵解法

ncdx2009

2016-04-04 15:54:50 +08:00

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