主题：【原创】从两个经典智力趣题谈起(一) -- 丁坎
家园 汗颜 的确是个TYPO，
应为
0，-1
已经更正，花谢王树兄提醒。
家园 附记：奥运开幕前夕有感 糊里糊涂就到了奥运开幕式的前一天，想想我来到西西河，也是奥运的缘故。当初因为圣火传递时发生的种种事件，满腔愤懑而无能为力，只得在网上搜寻一切相关信息。搜到西西河来时，恰好读到一个朋友的帖子，其中一段话让我感慨横生。
我在投名状中说过，自己上网时间很长，帖子却没发过几篇，原因呢，主要觉得自己卑之无甚高论，写出来也没有什么意思。读到那位朋友帖子中的话时，突然很有触动--，觉得写点东西，哪怕对一个人有价值也没有白费，所以就来注册了。
今天离那时已经三个多月了，中间写了不少帖子，也认识了不少朋友(大约也得罪了不少朋友，呵呵)，别的不说，喜悦和欣慰时常还是有的。
今天这篇帖子，献给奥运，祝2008奥运顺风顺水，各国选手俱创佳绩。
也希望我们的祖国象保卫圣火期间重新传颂的歌词那样：
歌唱我们亲爱的祖国,从此走向繁荣富强
谢谢所有的朋友，特别是那篇帖子的作者。
家园 第一题是什么意思？没看懂 是您表述不清，还是我没理解？
假如你是老板，请了个工匠来替你完成一件需要7天完成的工作。谈好的工酬是一天一个金环，你手里有7个连在一起的金环，如何切分这7个金环，使得付酬可以顺利完成？要求是：
1 不得预支或拖欠，干完几天就刚好付出几个金环
2 切分次数越少越好
每天切个环当报酬就行了吧？切成1、2、4和这题有什么关系？
倒是第二题只要把所有可能性照顾到就行了。
家园 “切分次数越少越好”
家园 【原创】称球问题的另外证明。（一）【二色划分引理】 【描述】
i、 有Nb个黑球和Nw个白球，其总数N是个奇数。
ii、现在要从中挑出M个球（M为偶数，M≤N-1），满足这个条件：
其中的黑球个数Mb是偶数，白球个数Mw也是偶数。M=Mb+Mw。
（Nb、Nw 以及M 这三个数的数值是事先给定的；而Mb和Mw的取值有自由度，仅需满足：“是偶数”，以及“相加为M” 这两个约束条件即可）。
【引理】对于任意的和为奇数的Nb和Nw，以及任意的偶数M＜Nb+Nw，前述任务都是可以达成的。
【证明】
不失一般性，假设Nw＞Nb（Nw≠Nb，因为Nb+Nw 是奇数）。
先尽量选黑球，从0直到最大可能的偶数 Nb0 = 2×floor(Nb/2)。 [floor(x) 是取x的整数部分，例如floor(4.9) = 4。]
如果M∈[0, Nb0]，那么任务就可以完成了。
如果M＞Nb0，那么我们再接着取 Nw1 = M－Nb0 个白球，即可完成任务。 因为M和Nb0都是偶数，所以Nw1也是偶数。另外，也不难证明Nw1≤Nw。
所以任务完成。证毕。
【例子】假设有3个黑球，4个白球，要选满足条件（ii）的6个球。
做法：先取2个黑球，这就到黑球数为偶数的顶了。再接着取4个白球，即可完成任务。
家园 【原创】称球问题的另外证明。（二）【称球引理1】 【描述】有 N = 3^n（3的n次方）个球，为方便以后的描述起见，将它们排好序。已知的信息是：其中有一个坏球；并且这个坏球出现的位置及其轻重，可归类为下列两种情况：
1、如果坏球出现在前‘N+’个位置上（1，……，N+），那么坏球重于好球。
2、如果坏球出现在后‘N-’个位置上（N+，……，N），那么坏球轻于好球。
（N+和N-这两个数是已知的，N+ + N- = N。）
有一台只能给出{“左重”、“平衡”、“左轻”}指示的天平。
【称球引理1】称量n次，便可将那个坏球所在的位置找出来（由题设，一旦确定其位置，那么亦马上可知其为轻或为重）。
【证明】
（A）当 n=0 时，就是说，有 N = 3^0 = 1 个球，已知其中有一个坏球（并且N+也是已知的，其取值为0或1。譬如若N+=0，那么坏球必然轻于好球，因为坏球位于1，排在N+的后面），这就意味着，坏球的位置及轻重都是已知的。所以不需称量，就已经知道结果了。故而所需的称量次数为0。
（B）设 n=K 时，命题成立。
（C）当 n=K+1，我们在 N= 3^(K+1) 个球中，选出 M= 2 × 3^K 个球，条件是：其中可能是轻球的个数，以及可能是重球的个数，都是偶数。（由“二色划分引理”，这是可以做到的。）既然它们都是偶数个，那就可以各自分为两半，在天平的左右托盘各放一半。
例如，假设我们选出了总共 M=6 个球，其中两个可能为轻球，四个可能为重球。那么我们将可能为轻球的那两个，分成两个子集，在天平的左右托盘各放其一；将可能为重球的那四个，亦类似地分成两半。就是说，在天平的左右托盘各放1个可能是轻球的球，以及2个可能是重球的球。
现在，天平的设置为：左盘有{QQ……Q，Z……Z}，右盘有{qq……q，z……z}。其中，‘Q’表示可能是轻球；‘Z’表示可能是重球。大写字母表示在左盘，小写字母表示在右盘。由划分方法，“QQ……Q”的个数等于“qq……q”的个数；“Z……Z”的个数等于“z……z”的个数。
我们进行称量，假设结果是“平衡”，那就说明，坏球只能在没被选中的那 N-M = 3^K 个球中。我们还剩下K次称量，由（B），我们可以从中找出坏球。
假设结果是“左轻”，那就说明，“Z……Z” 和 “qq……q” 那些球肯定是好的（因为不然的话，假设坏球是“Z……Z”或“qq……q”其中之一，那就应该左端为重、右端为轻才对），那些未被选中的 N-M = 3^K 个球 也都洗脱了嫌疑，因为罪魁祸首可以确定是在 “QQ……Q” 或者 “z……z”之中。 这些仍有嫌疑的球总共有多少个呢？ 正好 3^K 个！因为“QQ……Q”和“z……z”各为选中的轻、重球的一半，所以它们的和就是选中的球总数的一半，就是 M/2 = 3^K。 我们现在还剩下K次称量，由（B），可以从中找出坏球。
假设结果是“左重”，推理类前。
引理证毕。
家园 【原创】称球问题的另外证明。（三）【称球引理2】 【描述】有 N =（3^n - 1）/2 个球，其中可能有一个坏球。（坏球可能比好球轻、也可能比好球重。）我们手头还有一个已知的好球。
有一台只能给出{“左重”、“平衡”、“左轻”}指示的天平。
【称球引理2】称量n次，便可确定：有没有坏球，若有，坏球在哪儿，它比好球轻还是重？
【证明】
分析：这N个球可能的状况共有 1 + 2×N = 3^n 个。（‘1’：没有坏球；‘2×N’：坏球在1……N个位置上，每个位置上还有轻或重两种可能。） 称量n次能给出的信息就是 3^n 个（不取log2()）。所以，这个N是n次称量所能确定结果的球数上确界。 同样地，“称球引理1”也是上确界。
（A）当n=1，那么N=1，将它和手头的好球用天平作比较，就知道结果了。
（B）设n=K，命题成立。
（C）当n=K+1，我们如此来划分那N个球：
留着 N0 = （3^K - 1）/2 个球不选，选中的是 N - N0 = （3^(K+1) - 1）/2 - （3^K - 1）/2 = (3^(K+1) - 3^K)/2 = (3× 3^K - 3^K)/2 = 3^K. 这是奇数，无法分成相等个数的两份，放在天平的左右边。不用急，这时那个好球正好可以派上用场了。将那 3^K 个球，连同一个好球，划分成两份（每份有(3^K+1)/2个球），放在天平的两端。进行称量。
假设结果是“平衡”，那么那个可能的坏球只能在那留下的N0个球中。我们还剩K次称量，由（B），保证可以完成任务。
假设结果是“左重”，那么那个必然的坏球就在天平上的 N - N0 个球中，我们就可以给这些球贴上标签，凡是在左端的球，都贴上“可能重”的标签；凡是在右端的球，都贴上“可能轻”的标签。（好球不用贴标签了。） 那么我们手头的问题是： 3^K 个有标签的球，需要称量K次，将坏球（及其轻重）找出来。由“称球引理1”，这是可以完成的。
假设结果是“左轻”，推理类前。
引理证毕。
家园 【原创】称球问题的另外证明。（四）【主定理】 【描述】有 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 进行称量的不同次数之间不应该分开考虑，而必须作为一个整体考虑。
在这个背景下，我们可以想到，每次称量可以提供三种结果，N次称量可以提供的可能性是3的
N次方。考察一下3的2次方9与可分辨数3，3的3次方27与可分辨数12之间的关系，不难求得
可分辨数= (3的N次方-3)/2
这个公式的涵义是什么呢？
赝品在每次称量时有三种可能：左盘，右盘，不选
反过来，这三种可能在赝品轻重确定的情况下，将直接确定天平的状态。
比如说，赝品重于真品，则赝品的
左盘，右盘，不选
直接确定天平的
左重，右重，平衡
若赝品轻于真品，则刚刚相反。
这时我们明白，几乎每一组天平测量结果都可以确定一个赝品及其轻重，尽管我们此时还不明白减3的涵义，但已经可以确定这种思路的正确性了。
有了思路之后，还要找出具体的执行方案，也希望在具体方案中找到减3的原因。
以称三次为例(呵呵，我当时就是直接硬求出来的，并没有想到求助于称两次)，我的思路是：
A
分别以1，0，-1标记一颗珍珠在某次称量时的状态：左盘，不选，右盘
以一个三维数值矢量来标记某颗珍珠的三次称量称量，
如1，1，1 则表示这颗珍珠每次都被放入左盘。
共有27个可能的数值矢量。
以左，平，右标记天平的一次称量结果：左重，平衡，右重
(其实用1，0，-1是一样的，但我当时脑袋被折腾晕了，不想再费脑浆去转换，所以用了更直观的记法。)
以一个三维字符矢量来标记天平三次称量结果，
如左，左，左则表示天平三次称量结果都是左盘更重。
共有27种可能的字符矢量。
现在的问题是要用27个数值矢量去标记珍珠，以找出赝品，
让我们来看看，这种标记需要满足些什么条件：
首先，要区分一颗珍珠与另一颗珍珠，另一颗珍珠必须拥有不同的矢量，
否则无法根据三次测量结果来区分则两颗珍珠。
所以，12颗珍珠应该拥有彼此不同的数值矢量。
其次，如果两颗珍珠每次取用状态完全相反，则无法判断是此重还是彼轻，
所以，一旦一个数值矢量被选中，由它取反而得的矢量就该被排除
比如说1，0，1被选中，-1，0，-1就该被排除。否则当称量结果为左平左时，我们无法判断
是1，0，1重于真品，还是-1，0，-1轻于真品。
也就是说，除000外的26个数值矢量可以被分成互为取反的13对，每对只能有一个被选用。
其实分析到了这里，也就明白了减去000是必然的，因为一旦它被选用，就意味着某颗珍珠根本没有参与称量，如果它恰好是赝品，我们就无从知道它比真品重还是轻。
再次，被选用的12个数值矢量相加，总和必须是0，0，0，这是要求天平左右两盘的珍珠数必须相等，这样才能保证天平称量的重量差别是由赝品与珍品的重量差别迎起的，而不是由左盘3颗右盘4颗那样的数量差别引起的。
当时就根据这三条标准，再减去0，0，0，并连带的减去极端情况的思路，把1，1，1和-1，-1，-1减去，(其实这两个矢量可以不排除)从24个可能的数值矢量中凑出了满足三标准的12个矢量，从而得到一个解。
硬凑很久之后，终于得到一个解答，虽然颇有成就感，但也累得精疲力竭。
所以后来我又狠狠地思考了一番，是否有一种方便快捷的方法，无论称量次数是多少，都可以迅速求出一组解，很幸运地是，这种方法被我找到了。
呵呵，喝口水先。
(使用尽量中文 兄的思路和我很接近，只是我用 +1，-1 代表左右似乎更直观一些，在第二，三个条件的表达上
一旦一个数值矢量被选中，由它取反而得的矢量就该被排除被选用的12个数值矢量相加，总和必须是0，0，0，也比较好理解。
使用尽量中文 兄 直接使用三进制编码应该也有一些优越性，他在寻求12个数值矢量时就不再是纯粹的拼凑，而有一套固定的程序，可惜我看得不太懂，也无法确证它在数学上的正确性，
特别是称量次数较大的时候。)
家园 从两个经典智力趣题谈起(三) 要讲《太玄经》，先来说说它的作者扬雄扬子云。扬雄在今天的知名度不太高，很多人甚至记得 陋室铭 中那句 西蜀子云亭 而仍然不知道扬雄何许人也。其实扬雄是个牛人，
智慧多得在任何一个方向都可以满溢而畅流的那种大牛人。雕虫小技这个常用语就源自他的自述-----他本来以文章辞赋名世，后来觉得这些东东技术含量太低，干脆声称那只是自己小时候玩玩而已，大了不玩这些。 那他玩什么呢？ 什么都玩，见牛人就PK，当世的人大多服了他，没人有资格成为他的挑战对象，所以他憋得只好找古代的牛人PK。
汉书是这样记载的：
其意欲求文章成名于后世，以为经莫大于《易》，故作《太玄》；传莫大于《论语》，作《法言》；史篇莫善于《仓颉》，作《训纂》；箴莫善于《虞箴》，作《州箴》；赋莫深于《离骚》，反而广之；辞莫丽于相如，作四赋；皆斟酌其本，相与放依而驰骋云。(词赋方面的创作只是是他早期的作为，上面那个单子还遗漏了一部他为了PK《尔雅》而写的的重要著作---《方言》
《輶轩使者绝代语释别国方言》简称《方言》，扬雄著，是中国第一部记录方言的著作，是中国语言学史上一部里程碑式的著作，成为世界上第一部方言比较词汇集而开方言地理学之先河。
)
他PK易经的作品就是我们今天要谈的《太玄经》，这部书写出来后，
刘歆亦尝观之，谓雄曰：“空自苦！今学者有禄利，然向不能明《易》，又如《玄》何？吾恐后人用覆酱瓿也。”意思是说，今天这些学者白吃官饭，连易经都搞不明白，能拿你的《太玄经》怎样？我怕后人只好拿这部书去盖酱菜坛子。这部书的命运被刘歆不幸而言中，后世的人实在被《太玄经》搅得头大，用李白的话来说就是 白首太玄经，《太玄经》的义理没什么人理解，它的书名倒成了深奥难解的符号。(那个以砸缸成名的优秀儿童司马光长大后又与酱菜坛子过不去----写了《太玄经集注》，要把《太玄经》从酱瓿上解救出来，效果不明显)
《太玄经》简单地说就是扬雄用八十一块砖头构建的一座自然哲学殿堂，要理解这座殿堂，最好的方法是对比这座殿堂与用六十四块砖头构建的另一座自然哲学殿堂----周易。
周易的六十四块块砖头就是六十四卦，每卦六个位置，每个位置有两种可能的符号：一长横或两短横___ _ _。
六个位置被称为六爻，爻位自下而上被称为：
初，二，三，四，五，六。每爻对应爻辞。
《太玄经》的八十一块砖头就是八十一首，每首四个位置，每个位置有三种可能的符号：一长横，两短横或三短横 ____ _ _ _ _ _。
四个位置自上而下被称为：
方，州，部，家。每个位置不直接对应辞句，而是每一首拥有自初至上的九赞。
首的数目等于3*3*3*3=81，赞的数目等于81*9=729，扬雄以两赞为一日(夜与昼)，再加上一点小的调整，从赞数变出365，即一年的天数，这样就把历法融入了这座殿堂，据说还融合了当时的两种天文学说浑天说和盖天说，此处不再详论，有兴趣者可自行阅读《太玄经》。
重点还是我们关心的进位制。
谈进制，就必须有高位低位之分，且通过进制表达出来的数根据其大小有顺序之分。
这两点，在扬雄的《太玄经》里有没有呢？
有！
首先，书中《玄数》篇写道：
家嬴入部，部嬴人州，州嬴入方，方嬴則玄。嬴就是满的意思，家，部，州，方就是从低位到高位的进位，(当然，方嬴則玄的玄并不是下一个高位，而只是说，整个《太玄》系统到此就圆满了)
其次，更直接的士，八十一首的顺序编次，由中至养，中为四个一长横，养为四个三短横
如果我们以一长横为0，二短横为1，三短横为2，
则可将中写为三进制数字0000=0，养写为2222=2*27+2*9+2*3+2*1=80
自中至养一共八十一首，其顺序与如上求得的数值大小完全一致，每一首的序数恰为其三进数值加1，同中养二例。
通过以上两点，可以确凿无疑的宣称《太玄经》蕴涵了三进制思想。
而以这两点为标准，可以说，断言邵雍之前的周易系统有二进制思想是不充分的。
珍珠问题的扩展将随后单独讨论，以方便那些对此问题兴趣特别浓厚的朋友。
扩展讨论完毕后将从数学回到哲学，综合讨论 周易，太玄，道德经 和 二进制，三进制的本体论意义。
家园 逐篇送了兄弟六朵花，终于见到宝了 恭喜：你意外获得【西西河通宝】一枚
鲜花已经成功送出。
此次送花为【有效送花赞扬，涨乐善、声望】