主题：【原创】从两个经典智力趣题谈起(一) -- 丁坎
家园 三次称12/13个球的方法 这里举个实例，三次称12/13个球的方法
首先编号，编号过程冗长无聊，大家完全可以跳到最后面看结果（ctrl+f查找“好了现在开始称”）。
第一步把0-26用三进制表示出来：
decimal ternary
0 000
1 001
2 002
3 010
4 011
5 012
6 020
7 021
8 022
9 100
10 101
11 102
12 110
13 111
14 112
15 120
16 121
17 122
18 200
19 201
20 202
21 210
22 211
23 212
24 220
25 221
26 222
在把其中互补的放在一块
#1 #2
000 222
001 221
002 220
010 212
011 211
012 210
020 202
021 201
022 200
100 122
101 121
102 120
110 112
111 111
调整一下编号1和编号2，除了000/222以外，让4个小球编号1的每一位上是0的数目和是2的数目相等。我用的方法是,先把编号中1的个数小于2的小球花插着标上0或1, 再让不为1的每一位除以2和它异或：
switch? #1 #2 1 2 3
0 001 221 0 0
1 002 220 1 1 0
0 010 212 0 0
x 011 211 x
1 012 210 1 0
0 020 202 0 1 0
1 021 201 1 0
0 022 200 0 1 1
1 100 122 1 1
x 101 121 x
0 102 120 0 1
x 110 112 x
剩下的3个x就等于它所在的列里1的个数被4减：
switch? #1 #2 1 2 3
0 001 221 0 0
1 002 220 1 1 0
0 010 212 0 0
1 011 211 0
1 012 210 1 0
0 020 202 0 1 0
1 021 201 1 0
0 022 200 0 1 1
1 100 122 1 1
0 101 121 0
0 102 120 0 1
1 110 112 1
如果一个小球被标为1，那么把它的编号1和编号2互换：
#1 #2
001 221
220 002
010 212
211 011
210 012
020 202
201 021
022 200
122 100
101 121
102 120
112 110
终于，我们用它给小球编号
#1 #2
1 001 221
2 220 002
3 010 212
4 211 011
5 210 012
6 020 202
7 201 021
8 022 200
9 122 100
a 101 121
b 102 120
c 112 110
好了现在开始称，每次称的时候，把所有编号1中第i位是0的放在左边，第i位是2的放在右边：
第一次称， 1368在左边，2457在右边
第二次称， 17ab在左边，2689在右边
第三次称， 2356在左边，89bc在右边
每次称完，如果左边重，记作0，右边重，记作2，一样重，记作1。称n此后得到的数字就是有问题小球的编号。如果是编号1，这个小球比其他小球重。如果是编号2，这个小球比其他小球轻。如果得到的数字是111，那么有问题的是从来没有称过的小球，也就是第13颗小球，但是我们不知道它轻还是重。
家园 提问 过程大致看明白了，不过还是有两个问题。
调整一下编号1和编号2，除了000/222以外，让4个小球编号1的每一位上是0的数目和是2的数目相等。问题1：每次称量，天平左右两边放的小球数目应该相等。所以调整编号1和编号2的目的，是为了让#1那列的12个小球的编号在每一位上都有相等的0和2。请问，0和2的数目是不是一定要为4（您给出的结果是每一位上0，1，2的数目均为4），有没有可能第二位上0和2的数目都为3，如果这样也成立，在第二次称量的时候，把#1列中所有编号的第二位是0的放在左边，第二位是2的放在右边即可。我们知道第一次称量的时候左右两边分别有4个小球，但第二次称量的时候左右两边可以分别有3个小球。问题2：我对调整的过程是知其然不知其所以然。能否解释一下，为什么
先把编号中1的个数小于2的小球花插着标上0或1, 再让不为1的每一位除以2和它异或然后剩下的3个x就等于它所在的列里1的个数被4减然后如果一个小球被标为1，那么把它的编号1和编号2互换就可以达到目的了呢？先多谢了。
家园 【原创】从两个经典智力趣题谈起(二)： 两个老题，会解的人不少，自然在我意料之中。
可是我想做的引申，也被衲子兄，枸杞子兄，王树兄等一一道破，实在让人踌躇，是继续下去，还是请这几位仁兄详述他们的想法。既然开了头，还是我先来把抛砖引玉进行到底吧，期待各位朋友继续指教。
为保持行文的完整性，还是先把答案提一下。
第一题比较简单，如njyd兄所说
切开第三环, 金链被分成一(开口的),二,四.三份,来回倒就行了第二题要复杂一些，但基本上也是一个穷尽一切可能性的耐心测试。
我记得作家朱苏进在小说 接近于无限透明 中也用过这个题目，并且也这样认识这个题目。
详细一点的解法如下：
将12颗珍珠标记为-12号，并分为1-4，5-8，9-12三组。
第一次 称量1-4和5-8，根据结果不同，分别讨论
1 如果第一次称量天平保持平衡，则赝品在9-12号中。
第二次称量9-11和1-3(真品)
1.1 如果天平继续保持平衡，则赝品为12号，第三次称量与任一真品比较则可得其轻重。
1.2 如果天平左盘更重，则赝品在9-11号中，且重于真品。
第三次称量9和10号，如果平衡，则赝品为11号。
如果左盘重，则赝品为9号，右盘重，则为10号。
1.3 如果天平右盘更重，则类似于左盘更重处理。
2 如果第一次称量时，左盘重于右盘，则赝品在1-8中。
第二次我们就称量1，2，3，5和4，9，10，11，(后三个已确定为真品)
2.1 如果此时天平保持平衡，则赝品在6-8中，且轻于真品，
第三次称量6和7，根据天平的左重，右重和平衡，可分别确定赝品为7，6和8。
2.2 如果在第二次称量时天平左重，则赝品在1-3中，且重于真品，
第三次称量1和2，根据天平的左重，右重和平衡，可分别确定赝品为1，2和3。
2.3如果在第二次称量时天平右重，则赝品可能为轻于真品的5或重于真品的4，
只需在第三次称量时任选其中之一与真品比较则可。
3 如果第一次称量时，左盘轻于右盘，则类似于左盘更重处理。
通过不断尝试穷尽一切可能性，这两道题总是可以解答出来的。
然而，如果仅仅满足于误打误撞出来的解答，在题目进行推广的情况下，就很容易束手无策。
比如说，我们将第一题中的金环数改为511，又该如何解答呢？
显然，此时完全从头开始进行尝试是不可取的----过多的可能性的一一试错使得人脑难以胜任。那么，该怎么办呢？------从原始题目的解答中寻找规律。
我们先来看看第一题的解答，分得的金环数分别为 1， 2， 4， 也就是2的0次，1次和2次方，而金环的总数是7，也就是2的3次方减1，这到底只是巧合呢，还是蕴涵了什么玄机？
让我们重新思考一下题目的要求和解答，我们发现，分金环的实质其实是把一个数N分成K部份，要求是用这些部份能够表达出所有小于等于N的数来，而且要让满足这个条件的部份数K最小。当然，主要限制条件在于部份数最少----如果没有这个条件，我把N分成N部份，每部份为1，当然可以表达出所有小于等于N的数。
有了部份数最少的要求，N部份的分法就肯定不可取了，但是，为什么这样分不可取呢？
直感告诉我们，这样分的话很多部份很多余。什么叫多余？在这里，多余究竟意味着什么？
N部份的分法中，有N-1个部份他们自身的值已经由别的部份表达出来了，这就导致了多余！
消除了所有的多余是什么情况？
是这种情况----K部份彼此不等，于是每一部份在表达一个数的时候都不可能重复出现，而只能在出现与不出现两种可能性之间选择其一。
出现，或者不出现，
这正是二进制中每个基本单位的特征。
对比一下十进制与二进制：
十进制的基本单位是1， 10， 100 ....
二进制的基本单位是1， 2， 4....
十进制中的基本单位可以重复，比如35，包括3个10和5个1
二进制中的基本单位不可重复，最高出现次数为1，于是只有两种可能，出现或者不出现。
所以，第一题中1，2，4与二进制之间的对应并非偶然，而是内在的铁律。
事实上，公认的二进制之父莱布尼兹先生在他1703年的论文
Explanation of Binary Arithmetic
写道：
Here, one glance makes evident the reason for a celebrated property of the geometric progression by twos in whole numbers, which holds that if one has only one of these numbers for each degree, one can compose from them all the other whole numbers below the double of the highest degree. For here, it is as if one said, for example, that 111, or 7, is the sum of four, two, and one, and that 1101, or 13, is the sum of eight, four, and one. This property enables assayers to weigh all sorts of masses with few weights and could serve in coinage to give several values with few coins.莱布尼兹先生清楚地注意到了二进制的一个特性：使用最少个数的基本单位来表达数字，
并用了一个形象的类比来表达这个特性----称数。
把一个待表达的数看作一个待称的物体，而把各种进位制的基本单位看作砝码，二进制总是能用最少的砝码来称量物体(数)。
以7为例，二进制只需3个砝码，而十进制需要7个砝码。
这里需要注意的是，莱布尼兹也把称数的范围表达得很清楚---all the other whole numbers below the double of the highest degree-低于某个基本单位的所有数，可以通过这个单位以下所有的单位的组合来表达。
第一题中这个数是7，低于8这个基本单位，而我做的扩展是511，低于512这个基本单位，只需要1，2，4，8，16，32，64，128，256这9个基本单位就可以全部得到表达。
既然说到了莱布尼兹和二进制，就不可避免地要谈到中西文化交流史上一桩公案：莱布尼兹和易经。这里我们也不去考据这桩公案的详细源流，这里只略谈两点：
1 探讨莱布尼兹二进制与易经的渊源具有思想史研究的意义，但是，如果要以此出发，认为易经包含了二进制乃至计算机的奥秘，想凭易经分得现代文明的红利，就是一种没出息的懒汉思想。持这种思想的人最好先去了解一下莱布尼兹之前西方人自己二进制思想的萌芽，了解一下什么叫图灵机，了解一下电子技术的发展历程。
2 莱布尼兹自以为自己与中国几千年前的圣人伏羲英雄所见略同，其实是一种误解。
他的出发点是二进制与他所见的伏羲六十四卦次序图之间的对应关系，不过，正如黄帝内经的作者不是黄帝，伏羲六十四卦次序图的作者也不是伏羲，而是宋朝的邵雍。
需要思考的是，我们如何区分二进制思想和普通的排列组合？
我们知道，把两个不同的东西在不同位置上进行排列组合不一定意味着二进制思想，比如说随便找个孩子，教他说大小，就是说着玩也很容易说出大大，小小，小大，大小这样的组合来，我们不能认为这孩子也拥有二进制思想吧。
所谓二进制，归根结底是数的一种表示方法。二进制思想和普通的排列组合之间的界限在于，
前者必须把得到的不同排列与不同的数对应起来，而且这种对应要与数的大小一致。
在这个意义上讲，伏羲六十四卦次序图可以认为已经包含了二进制思想，但此图年代较晚。
而出现年代早的六十四卦通行卦序，根本体现不出与数的一致(详见拙文 石破天惊
链接出处)，由此，我们并不能确证邵雍之前的易经系统已经蕴涵了二进制思想。这个看法可能让某些民族情感过于浓烈的朋友不快，不过，一个民族的崛起只能屹立在事实，而不是情感之上。
而且，也不用太过不快，按照前述的标准，我们马上会发现，远早于宋朝，在西汉时期，扬雄
写出的太玄经，就确凿无疑地蕴涵了三进制思想。
具体内容，留在下个帖子里与第二个题目的推广一起讨论。
家园 切环问题，须计入实践上的复杂性，2^k 序列未必是最优的 原因在于，当切破的环数（n0）大于一定数值时，那n0个环本身就提供了我们n0个1，因此我们可以不用再切出2个环、4个环……的链条（具体可以省去多少，取决于1的个数）。
例如，63个环的链条，我们须切几刀呢？只需3刀。依此法：
[4]⊙[8]⊙[16]⊙[32]，其中[n]表示长度为n的链条；⊙表示切破的一个环。
2047个环的链条，只需切7刀：
[8]⊙[16]⊙[32]⊙[64]⊙[128]⊙[256]⊙[512]⊙[1024]
(七个1，加上8、16、32、……）
本帖一共被 2 帖 引用 (帖内工具实现)