主题：【原创】从两个经典智力趣题谈起(一) -- 丁坎
【描述】有 N =（3^n - 3）/2 个球，其中可能有一个坏球。（坏球可能比好球轻、也可能比好球重。）
有一台只能给出{“左重”、“平衡”、“左轻”}指示的天平。
【称球定理】称量n次，便可确定：有没有坏球，若有，坏球在哪儿，它比好球轻还是重？
【证明】
分析：这与“称球引理2”的差别在于，现在我们手头没有好球了，致使N比上确界少1。
我们这样来划分这N个球：
留着 N0 = （3^(n-1) - 1）/2 个球不选，选中的是 N - N0 = （3^n - 3）/2 - （3^(n-1) - 1）/2 = (3^n - 3^(n-1) -2)/2 = 3^(n-1) - 1. 这是个偶数，因此可以分成两份，放在天平左右端。进行称量。
假设结果是“平衡”，那么那个可能的坏球只能在那留下的 N0=（3^(n-1) - 1）/2 个球中。而且，我们手头有了好球（天平上的就是），于是便可运用“称球引理2”（“称球引理2”给出的是上确界）。于是，剩下的n-1次称量，保证可以完成任务。
假设结果是“左重”，那么依照在“称球引理2”的证明中的方法，给天平上的球贴标签。于是，我们有3^(n-1)-1 个贴有标签的球，还能称量n-1次，由“称球引理1”，这是可以完成的。（实际要求比“称球引理1”所给出的上确界还宽松。）
假设结果是“左轻”，推理类前。
定理证毕。
Q.E.D. (Quite Easily Done :-)
是您表述不清，还是我没理解？
要求是：
1 不得预支或拖欠，干完几天就刚好付出几个金环
2 切分次数越少越好
每天切个环当报酬就行了吧？切成1、2、4和这题有什么关系？
倒是第二题只要把所有可能性照顾到就行了。
崩溃，辛辛苦苦把错改了，却撞上又一次改版，无法上传图片，只好先把旧的版本删除，以免谬种流传。
简单文字叙述一下，解决称量N次的办法，就是三步走：
1 定BASE
找张纸出来，在上面写下
1，0
-1，1
0，-1
三行数字
2 举一反三
把前面所得的行数扩充为原来的三倍，方法是在每行首位添上1，0，-1。
3 缺额填充
在举一反三所得的行下面，再写三行，首位分别为1，0，-1，后面分别用0，-1，1填满。
(使该行数字总数与其他行数字总数相等)
1, 0, 0, ... 0
0, -1, -1, ... -1
-1, 1, 1, ... 1
剩下的就是反复进行2，3两个步骤，直到每行数字个数等于N。
此时每行代表一个小球，读取每行，在第几个位置上数字分别为1，0，-1，则意味着该球在第几次称量中被
放在左盘，未被选用和放在右盘。
如此确定的安排，将使得最终天平的称量结果与次品小球及其轻重一一对应。
简单吧，不需要动脑筋吧，纯粹一机械劳动。
我写了个小程序，测试结果如下：
可测试的小球数为： 12
现在显示小球取用安排：
1 2 3 10
7 8 9 12
1 4 7 12
2 5 8 11
2 5 8 12
3 6 9 11
现在显示历次称量结果，L为左重，R为右重，E为平衡：
LLE
RRE
LRL
RLR
LER
REL
ELE
ERE
ERL
ELR
EER
EEL
RLE
LRE
RRL
LLR
RER
LEL
LEE
REE
ERR
ELL
RLL
LRR
恭喜，此次测试正确无误。
可测试的小球数为： 39
现在显示小球取用安排：
1 2 3 4 5 6 7 8 9 10 11 12 37
25 26 27 28 29 30 31 32 33 34 35 36 39
1 2 3 10 13 14 15 22 25 26 27 34 39
7 8 9 12 19 20 21 24 31 32 33 36 38
1 4 7 12 13 16 19 24 25 28 31 36 39
2 5 8 11 14 17 20 23 26 29 32 35 38
2 5 8 12 14 17 20 24 26 29 32 36 39
3 6 9 11 15 18 21 23 27 30 33 35 38
现在显示历次称量结果，L为左重，R为右重，E为平衡：
LLLE
RRRE
LLRL
RRLR
LLER
RREL
LELE
RERE
LERL
RELR
LEER
REEL
LRLE
RLRE
LRRL
RLLR
LRER
RLEL
LLEE
RREE
LERR
RELL
LRLL
RLRR
ELLE
ERRE
ELRL
ERLR
ELER
EREL
EELE
EERE
EERL
EELR
EEER
EEEL
ERLE
ELRE
ERRL
ELLR
ERER
ELEL
ELEE
EREE
EERR
EELL
ERLL
ELRR
RLLE
LRRE
RLRL
LRLR
RLER
LREL
RELE
LERE
RERL
LELR
REER
LEEL
RRLE
LLRE
RRRL
LLLR
RRER
LLEL
RLEE
LREE
RERR
LELL
RRLL
LLRR
LEEE
REEE
ERRR
ELLL
RLLL
LRRR
恭喜，此次测试正确无误。
可测试的小球数为： 120
现在显示小球取用安排：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 118
79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 120
1 2 3 4 5 6 7 8 9 10 11 12 37 40 41 42 43 44 45 46 47 48 49 50 51 76 79 80 81 82 83 84 85 86 87 88 89 90 115 120
25 26 27 28 29 30 31 32 33 34 35 36 39 64 65 66 67 68 69 70 71 72 73 74 75 78 103 104 105 106 107 108 109 110 111 112 113 114 117 119
1 2 3 10 13 14 15 22 25 26 27 34 39 40 41 42 49 52 53 54 61 64 65 66 73 78 79 80 81 88 91 92 93 100 103 104 105 112 117 120
7 8 9 12 19 20 21 24 31 32 33 36 38 46 47 48 51 58 59 60 63 70 71 72 75 77 85 86 87 90 97 98 99 102 109 110 111 114 116 119
1 4 7 12 13 16 19 24 25 28 31 36 39 40 43 46 51 52 55 58 63 64 67 70 75 78 79 82 85 90 91 94 97 102 103 106 109 114 117 120
2 5 8 11 14 17 20 23 26 29 32 35 38 41 44 47 50 53 56 59 62 65 68 71 74 77 80 83 86 89 92 95 98 101 104 107 110 113 116 119
2 5 8 12 14 17 20 24 26 29 32 36 39 41 44 47 51 53 56 59 63 65 68 71 75 78 80 83 86 90 92 95 98 102 104 107 110 114 117 120
3 6 9 11 15 18 21 23 27 30 33 35 38 42 45 48 50 54 57 60 62 66 69 72 74 77 81 84 87 89 93 96 99 101 105 108 111 113 116 119
现在显示历次称量结果，L为左重，R为右重，E为平衡：
LLLLE
RRRRE
LLLRL
RRRLR
LLLER
RRREL
LLELE
RRERE
LLERL
RRELR
LLEER
RREEL
LLRLE
RRLRE
LLRRL
RRLLR
LLRER
RRLEL
LLLEE
RRREE
LLERR
RRELL
LLRLL
RRLRR
LELLE
RERRE
LELRL
RERLR
LELER
REREL
LEELE
REERE
LEERL
REELR
LEEER
REEEL
LERLE
RELRE
LERRL
RELLR
LERER
RELEL
LELEE
REREE
LEERR
REELL
LERLL
RELRR
LRLLE
RLRRE
LRLRL
RLRLR
LRLER
RLREL
LRELE
RLERE
LRERL
RLELR
LREER
RLEEL
LRRLE
RLLRE
LRRRL
RLLLR
LRRER
RLLEL
LRLEE
RLREE
LRERR
RLELL
LRRLL
RLLRR
LLEEE
RREEE
LERRR
RELLL
LRLLL
RLRRR
ELLLE
ERRRE
ELLRL
ERRLR
ELLER
ERREL
ELELE
ERERE
ELERL
ERELR
ELEER
EREEL
ELRLE
ERLRE
ELRRL
ERLLR
ELRER
ERLEL
ELLEE
ERREE
ELERR
ERELL
ELRLL
ERLRR
EELLE
EERRE
EELRL
EERLR
EELER
EEREL
EEELE
EEERE
EEERL
EEELR
EEEER
EEEEL
EERLE
EELRE
EERRL
EELLR
EERER
EELEL
EELEE
EEREE
EEERR
EEELL
EERLL
EELRR
ERLLE
ELRRE
ERLRL
ELRLR
ERLER
ELREL
ERELE
ELERE
ERERL
ELELR
EREER
ELEEL
ERRLE
ELLRE
ERRRL
ELLLR
ERRER
ELLEL
ERLEE
ELREE
ERERR
ELELL
ERRLL
ELLRR
ELEEE
EREEE
EERRR
EELLL
ERLLL
ELRRR
RLLLE
LRRRE
RLLRL
LRRLR
RLLER
LRREL
RLELE
LRERE
RLERL
LRELR
RLEER
LREEL
RLRLE
LRLRE
RLRRL
LRLLR
RLRER
LRLEL
RLLEE
LRREE
RLERR
LRELL
RLRLL
LRLRR
RELLE
LERRE
RELRL
LERLR
RELER
LEREL
REELE
LEERE
REERL
LEELR
REEER
LEEEL
RERLE
LELRE
RERRL
LELLR
RERER
LELEL
RELEE
LEREE
REERR
LEELL
RERLL
LELRR
RRLLE
LLRRE
RRLRL
LLRLR
RRLER
LLREL
RRELE
LLERE
RRERL
LLELR
RREER
LLEEL
RRRLE
LLLRE
RRRRL
LLLLR
RRRER
LLLEL
RRLEE
LLREE
RRERR
LLELL
RRRLL
LLLRR
RLEEE
LREEE
RERRR
LELLL
RRLLL
LLRRR
LEEEE
REEEE
ERRRR
ELLLL
RLLLL
LRRRR
恭喜，此次测试正确无误。
我可以自信地断言，这是迄今为止最简单的解法：
不论称量次数多高，都转化成3个球称量两次的问题来处理(而这，够简单了吧)，其他完全不费吹灰之力。
需要说明的是，为了严格起见，使用了数学符号，但其实质内容都很初等，不要被吓倒了。
看图吧。
[QUOTE][/QUOTE]
糊里糊涂就到了奥运开幕式的前一天，想想我来到西西河，也是奥运的缘故。当初因为圣火传递时发生的种种事件，满腔愤懑而无能为力，只得在网上搜寻一切相关信息。搜到西西河来时，恰好读到一个朋友的帖子，其中一段话让我感慨横生。
我在投名状中说过，自己上网时间很长，帖子却没发过几篇，原因呢，主要觉得自己卑之无甚高论，写出来也没有什么意思。读到那位朋友帖子中的话时，突然很有触动--，觉得写点东西，哪怕对一个人有价值也没有白费，所以就来注册了。
今天离那时已经三个多月了，中间写了不少帖子，也认识了不少朋友(大约也得罪了不少朋友，呵呵)，别的不说，喜悦和欣慰时常还是有的。
今天这篇帖子，献给奥运，祝2008奥运顺风顺水，各国选手俱创佳绩。
也希望我们的祖国象保卫圣火期间重新传颂的歌词那样：
歌唱我们亲爱的祖国,从此走向繁荣富强
谢谢所有的朋友，特别是那篇帖子的作者。
过程大致看明白了，不过还是有两个问题。
问题2：我对调整的过程是知其然不知其所以然。能否解释一下，为什么
12/13个小球，除了000,111,222外，每个球分配到两个编码，每次称，所有相应位不为1的都应该被称到，否则对应的编码就不可能出现。而每位不为1的数字共有8个，两边放数目相等的小球，只能是一边4个
这个严格的证明就免了吧。基本思想，每个编码不一样，有的编码三位都不是1，他们调整一下牵连甚广，三位上2和0的总数都要变，所以先动它们。有的编码只有一位，所以直到最后一步再用它们来填缝。
恭喜：你意外获得【西西河通宝】一枚
鲜花已经成功送出。
此次送花为【有效送花赞扬，涨乐善、声望】
这两个问题的一般化——表示问题可以说是非常重要，俺也很感兴趣，本想谈谈心得体会的，可惜衲子兄在沙发上一语道破了，不知说些什么好，就耐心等丁坎兄的好文了，果然丁兄能给出俺心目中的答案（不敢说俺和丁兄英雄所见略同，因为有下面的信息，呵呵）
上海教育出版社的通俗数学名著译丛系列中有一本《蚁迹寻踪及其他数学探索》是译自david gale 的tracking the automatic ant and other mathematical exploeration 1998年spriger出版，收集了作者1991-1996年主持《数学信使》（mathematical intelligecer）上的数学娱乐（mathematical entertainments）专栏，其中的第12章donald j. newman给出了称硬币问题的表示法答案，而且说了这么一句话——
任何时候，哪儿有一个用到分支推理的解决方案，哪儿就会有另一个不用它的解决方案（而且更简单更清爽）
他是针对jeremy bernstein在new yorker上说是否会用分支推理过程解决这个问题是认定具有数学天才的标志所说的。
俺从来都以为独立发现自然界的奥秘是快乐和值得尊敬的，丁兄和俺都是
本帖一共被 3 帖 引用 (帖内工具实现)
1，0
-1，1
0，1
鲜花已经成功送出。
此次送花为【有效送花赞扬，涨乐善、声望】
此为西西河的态度。
任何时候，哪儿有一个用到分支推理的解决方案，哪儿就会有另一个不用它的解决方案（而且更简单更清爽）
我要加一个：独立发现人生的奥秘也是快乐和值得尊敬的。