3进制的天平称球问题

apkstore
enjoy tennis 10月22日 字数 939

看到有个家长问,新开一个帖子介绍下。

题目假设有一个重球混入了其他26个普通球中,球的外形一样,怎么用天平3次把这个球称出来。

把这27个球分别编号,编号顺序为

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

假定天平左边重为1,右边重为2,平衡为0 。那么

第一次: 把9个首位为1的球放在天平左边,9个首位为2的球放在天平右边,记录首位的实际数值;

第二次: 把9个次位为1的球放在天平左边,9个次位为2的球放在天平右边,记录次位的实际数值;

第三次: 把9个末位为1的球放在天平左边,9个末位为2的球放在天平右边,记录末位的实际数值;

最后把三个位的实际数值合起来就是该重球的编号了,比如第一次平,第二次左边重,第三次右边重。

那么重球就应该 012 第6个球。

这个题目其实利用了用三进制建模的思想把重球所在不同位置的三种状态转换成3进制的0,1,2 三个值。所以如果已知球重还是轻的话,称K次可以从 3的K次方个球中找到该球。

如果不知道球的轻重就比较复杂些,每个球对应着两个编码,而且要跑去000这种无法分辨的球,所以只能从(3的K次方-1)/2 中找到。

ChildEducation 儿童教育
63 个回复
xuanzhuan
旋转-迷失 10月22日

天呐,

1、很神奇

2、看不懂

发自「今日水木 on iPhone X」

【 在 apkstore 的大作中提到: 】

: 看到有个家长问,新开一个帖子介绍下。

: 题目假设有一个重球混入了其他26个普通球中,球的外形一样,怎么用天平3次把这个球称出来。

: 把这27个球分别编号,编号顺序为

: 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

: 假定天平左边重为1,右边重为2,平衡为0 。那么

: 第一次: 把9个首位为1的球放在天平左边,9个首位为2的球放在天平右边,记录首位的实际数值;

: 第二次: 把9个次位为1的球放在天平左边,9个次位为2的球放在天平右边,记录次位的实际数值;

: 第三次: 把9个末位为1的球放在天平左边,9个末位为2的球放在天平右边,记录末位的实际数值;

: 最后把三个位的实际数值合起来就是该重球的编号了,比如第一次平,第二次左边重,第三次右边重。

: 那么重球就应该 012 第6个球。

: 这个题目其实利用了用三进制建模的思想把重球所在不同位置的三种状态转换成3进制的0,1,2 三个值。所以如果已知球重还是轻的话,称K次可以从 3的K次方个球中找到该球。

: 如果不知道球的轻重就比较复杂些,每个球对应着两个编码,而且要跑去000这种无法分辨的球,所以只能从(3的K次方-1)/2 中找到。

: --

U2000
Untouchable 10月23日

这个有点绕啊

【 在 apkstore 的大作中提到: 】

: 看到有个家长问,新开一个帖子介绍下。

: 题目假设有一个重球混入了其他26个普通球中,球的外形一样,怎么用天平3次把这个球称出来。

: ....................

angrycm
angrycm 10月23日

为什么是3k-1/2 1是000,2是对应两种编码?

我记得有13个不知轻重的球能3次称出的题,但一直不知道是怎么操作的,您可否以类似方式演示下

发自「今日水木 on iPhone 8 Plus」

【 在 apkstore 的大作中提到: 】

: 看到有个家长问,新开一个帖子介绍下。

: 题目假设有一个重球混入了其他26个普通球中,球的外形一样,怎么用天平3次把这个球称出来。

: 把这27个球分别编号,编号顺序为

: 000

: 001

: 002

: 010

: 011

: 012

: ..................

tokilltime
tokilltime 10月23日

这种题我有生以来就没搞明白过……

【 在 apkstore 的大作中提到: 】

: 看到有个家长问,新开一个帖子介绍下。

: 题目假设有一个重球混入了其他26个普通球中,球的外形一样,怎么用天平3次把这个球称出来。

: 把这27个球分别编号,编号顺序为

: ...................

wangychf
车夫 10月23日

牛!

【 在 apkstore 的大作中提到: 】

: 看到有个家长问,新开一个帖子介绍下。

: 题目假设有一个重球混入了其他26个普通球中,球的外形一样,怎么用天平3次把这个球称出来。

: 把这27个球分别编号,编号顺序为

: ...................

ssora
Allah Akbar 10月23日

这种东西大部分成人都不会懂, 现在反而普遍地拿去教小孩。

这玩意以前是码农面试题, 类似的, 还有用猪去分辨毒药水。

【 在 tokilltime 的大作中提到: 】

: 这种题我有生以来就没搞明白过……

Mia
大有他娘麦子姑娘 10月23日

这种难道不是

第一次随便分成9个一堆,随便拿两堆称重,如果一样,说明第三堆重。

然后重的那堆随便分成3个一堆,重复

最后重的再分成一个算一组,重复

【 在 apkstore (enjoy tennis) 的大作中提到: 】

: 看到有个家长问,新开一个帖子介绍下。

: 题目假设有一个重球混入了其他26个普通球中,球的外形一样,怎么用天平3次把这个球称出来。

: 把这27个球分别编号,编号顺序为

: ...................

Realpig
小毛兔你好 10月23日

除了解法看起来太接地气,不炫,其他没问题呀

【 在 Mia 的大作中提到: 】

: 这种难道不是

: 第一次随便分成9个一堆,随便拿两堆称重,如果一样,说明第三堆重。

: 然后重的那堆随便分成3个一堆,重复

: ...................

Zziizi
Zziizi 10月23日

我记得2年级奥数有这样的题目,就是这样的算法。

【 在 Mia 的大作中提到: 】

: 这种难道不是

: 第一次随便分成9个一堆,随便拿两堆称重,如果一样,说明第三堆重。

: 然后重的那堆随便分成3个一堆,重复

: ....................

miaoha
miaoha 10月23日

三进值秒懂,以前觉得好神奇。

【 在 apkstore 的大作中提到: 】

: 看到有个家长问,新开一个帖子介绍下。

: 题目假设有一个重球混入了其他26个普通球中,球的外形一样,怎么用天平3次把这个球称出来。

: 把这27个球分别编号,编号顺序为

: 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

: 假定天平左边重为1,右边重为2,平衡为0。那么

: 第一次:把9个首位为1的球放在天平左边,9个首位为2的球放在天平右边,记录首位的实际数值;

: 第二次:把9个次位为1的球放在天平左边,9个次位为2的球放在天平右边,记录次位的实际数值;

: 第三次:把9个末位为1的球放在天平左边,9个末位为2的球放在天平右边,记录末位的实际数值;

: 最后把三个位的实际数值合起来就是该重球的编号了,比如第一次平,第二次左边重,第三次右边重。

: 那么重球就应该012第6个球。

: 这个题目其实利用了用三进制建模的思想把重球所在不同位置的三种状态转换成3进制的0,1,2三个值。所以如果已知球重还是轻的话,称K次可以从3的K次方个球中找到该球。

: 如果不知道球的轻重就比较复杂些,每个球对应着两个编码,而且要跑去000这种无法分辨的球,所以只能从(3的K次方-1)/2中找到。

littleSram
littleSram 10月23日

你的成功不可复制啊

学习了

【 在 apkstore 的大作中提到: 】

: 看到有个家长问,新开一个帖子介绍下。

: 题目假设有一个重球混入了其他26个普通球中,球的外形一样,怎么用天平3次把这个球称出来。

: 把这27个球分别编号,编号顺序为

: ...................

miaoha
miaoha 10月23日

三进值秒懂,以前觉得好神奇。

【 在 apkstore 的大作中提到: 】

: 看到有个家长问,新开一个帖子介绍下。

: 题目假设有一个重球混入了其他26个普通球中,球的外形一样,怎么用天平3次把这个球称出来。

: 把这27个球分别编号,编号顺序为

: 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

: 假定天平左边重为1,右边重为2,平衡为0。那么

: 第一次:把9个首位为1的球放在天平左边,9个首位为2的球放在天平右边,记录首位的实际数值;

: 第二次:把9个次位为1的球放在天平左边,9个次位为2的球放在天平右边,记录次位的实际数值;

: 第三次:把9个末位为1的球放在天平左边,9个末位为2的球放在天平右边,记录末位的实际数值;

: 最后把三个位的实际数值合起来就是该重球的编号了,比如第一次平,第二次左边重,第三次右边重。

: 那么重球就应该012第6个球。

: 这个题目其实利用了用三进制建模的思想把重球所在不同位置的三种状态转换成3进制的0,1,2三个值。所以如果已知球重还是轻的话,称K次可以从3的K次方个球中找到该球。

: 如果不知道球的轻重就比较复杂些,每个球对应着两个编码,而且要跑去000这种无法分辨的球,所以只能从(3的K次方-1)/2中找到。

Morpheus
勿臆、勿必、勿固、勿我 10月23日

理解的关键是问3个问题

重球编号的第一位是0,1还是2?

重球编号的第二位是0,1还是2?

重球编号的第三位是0,1还是2?

三次称量分别回答三个问题。

【 在 apkstore 的大作中提到: 】

: 看到有个家长问,新开一个帖子介绍下。

: 题目假设有一个重球混入了其他26个普通球中,球的外形一样,怎么用天平3次把这个球称出来。

: 把这27个球分别编号,编号顺序为

: ...................

haole99
haole99 10月23日

知道轻重这题就简单多了。难得是不知道轻重的题。如12球或者13球中混入一个不知轻重的一模一样的坏球,请问用天平称量几次可以将坏球找出,未经训练,能做出这种题的孩子都是牛蛙。

【 在 apkstore 的大作中提到: 】

: 看到有个家长问,新开一个帖子介绍下。

: 题目假设有一个重球混入了其他26个普通球中,球的外形一样,怎么用天平3次把这个球称出来。

: 把这27个球分别编号,编号顺序为

: ...................

kakapo7
鸮鹦鹉 10月23日

厉害啊,想到这种方法

【 在 apkstore 的大作中提到: 】

: 看到有个家长问,新开一个帖子介绍下。

: 题目假设有一个重球混入了其他26个普通球中,球的外形一样,怎么用天平3次把这个球称出来。

: 把这27个球分别编号,编号顺序为

: ...................

swp121cn
some 10月23日

这题目很简单,把球尽量分成三份(9,9,9)每次称两份,选出一份继续分成三份(3,3,3),如果不能平均分成三份,则根据最不利原则,选最多的分成三份,三次既可以找到重球,(9,9,9 )、(3,3,3 ),(1,1,1)

kakapo7
鸮鹦鹉 10月23日

学神,我有一题不会,你快帮我看看

能被11…11(共有2020个1)整除的正整数很多,对这些正整数分别求各位数字和,证明各位数字和的最小值是2020

【 在 apkstore 的大作中提到: 】

: 看到有个家长问,新开一个帖子介绍下。

: 题目假设有一个重球混入了其他26个普通球中,球的外形一样,怎么用天平3次把这个球称出来。

: 把这27个球分别编号,编号顺序为

: ...................

gloop
  10月23日

12个球中有一个重量不一样但不知是轻了还是重了,可以三次称出。13个球不行。这个问题就不是用三进制了。而是用信息论。一次称量得到3种可能,三次称量最多能区分出3x3x3 = 27种不同的情况。对于已知是轻了还是重了的情况,用三进制刚好能完美编码3次称量的结果。但对于12个球未知轻重,三进制就失去了用武之地。三进制只是技术,信息才是本质。

用信息论的求解要点是,一次称量最多区分出3种可能,两次称量最多区分出9种可能。因此第一次称量后必须保证未决定的信息不超过9种可能,第二次称量后未决定的信息不超过3种可能。比如13个球,如果按4、4、5分组,天平左边放4个,右边放4个,剩余5个。那么当天平平衡的时候,剩余5个球,不知道是轻了还是重了,总共有10种可能,剩余的信息量过大,不能用剩余的两次称量决定。如果按5、5、3分组,天平不平衡的时候剩余的可能也是10种,所以13个球不可能用3次称量决定。这里没有严格使用信息论的术语,但对中小学生来讲这样最容易理解。

编辑:后来有网友指出12球问题也可以用三进制,非常巧妙的构造,见 https://www.zhihu.com/question/20854512

关于13个球,如果需要判定异常的球是轻了还是重了,13个球是不可能的,证明就是我上面写的证明。但是如果不需要判定异常的球的轻重,则可以13个球,方法可以把第13个球放一边,完全按照12球的操作步骤,只要三次天平都是平衡,那就说明是第13个球有问题。另外还有一个变化问题,有13个球,另外还有很多已知是正常的球,那么也可以判定异常球的轻重。比如第一次称9个可能异常的球和9个已知正常的球,另外4个可能异常的球放一边,后面就简单了。

【 在 angrycm (angrycm) 的大作中提到: 】

: 为什么是3k-1/2 1是000,2是对应两种编码?

: 我记得有13个不知轻重的球能3次称出的题,但一直不知道是怎么操作的,您可否以类似方式演示下

: 发自「今日水木 on iPhone 8 Plus」

: ...................