[今天我们思考02]有这样一类题目...

[pongba]

有这样一类题目，它们的思路都有一个共性，就是在一堆条件中，有某个条件比其他条件更关键，从这个条件出发，只有有限的几种往下走的办法，通过穷尽这几种办法的尝试，答案往往就会迅速浮出水面。
不妨称这个启发法为"穷举/试错"启发法。

例如
1. 来自《如何求解问题，现代启发式方法》中的题：史密斯夫妇邀请另外四对夫妇就餐，已知他们每个人都不和自己握手、不和自己的配偶握手、且不和同一个人握手一次以上。在大家见面握手寒暄后，史密斯问大家握手了几次，每个人的答案都不一样。问：史密斯太太握手几次。
2. 来自一个pdf，Seven Puzzles You Think You Must Not Have Heard Correctly：Jan and Maria have fallen in love (via the internet) and Jan wishes to mail her a ring. Unfortunately,
they live in the country of Kleptopia where anything sent through the mail will be stolen unless it is enclosed in a padlocked box. Jan and Maria each have plenty of padlocks, but none to which the other has a key. How can Jan get the ring safely into Maria's hands?
3. 来自网络流传：12个球有一个重量不同，3次称出。
4. 来自网络流传（以及《编程之美》）：2堆橘子，m和n个。两人轮流拿。每个人拿的时候只能从其中一堆拿（不能跨堆拿），并且可以从他选定的那堆中拿走任意多个（0~剩下的所有）。那么，有无必胜策略，先后手有关系吗？
5. 来自伯克利的那个网址：一个标准圆柱体无盖透明杯子，里面似乎有半杯水，要你不借助任何工具，判定它是否精确地装了半杯水。
6. 来自一本奥林匹克数学竞赛题目集：n为奇数，现罗列出1,2,...2n这2n个数，然后我每次从中任取两个数a,b，并放回|a-b|，如此操作到只剩一个数，证明这个数一定是奇数。

P.S. 答案不是目的，思路才是目的。（为什么？）
知道更多相似题目的老大也请不吝跟贴:)

BTW. 在穷举有限的可能性的过程中人脑很容易犯一个错误，那就是忽略了某个关键的可能性，即落入思维陷阱。所以把思维的过程细致的写下来很重要，也许在某个环节上你想当然地认为下面一步肯定是A，然而通过细查写下来的思路你发现还有一种隐蔽的可能性。如果不写下来，是很难发现的。

--
刘未鹏(pongba)|C++的罗浮宫
http://blog.csdn.net/pongba
TopLanguage
http://groups.google.com/group/pongba

[xxmplus]

第5题不难，小时候就知道了，那时家里还有水井，这题是奶奶教我的，把桶倾斜直至水面碰到桶口，若这时水面也能碰到桶底，那就是正好一半，关键是水无常形，但体积不变。

说起这个，我想起小时候还看过这样两个题目：
1）在一个公车站，有红蓝两班车，他们都是10分钟一班，并且前后只差一分钟，理论上碰到两班车的概率应该是一样的，可是实际上你会发现基本上你在车站等车的时候老是等到同一种颜色的车，为什么？

2）有十堆零件，其中有一堆是次品，比正品的零件轻了1克，要求只能称一次，就把那堆次品找出来。

2008/4/10 pongba <pon...@gmail.com>:

--
Any complex technology which doesn't come with documentation must be the best
available.

[pongba]

2008/4/10 xxmplus <xxm...@gmail.com>:

第5题不难，小时候就知道了，那时家里还有水井，这题是奶奶教我的，把桶倾斜直至水面碰到桶口，若这时水面也能碰到桶底，那就是正好一半，关键是水无常形，但体积不变。

关键是奶奶的思路呢？试错？
我是试错试出来的。完整的思路我曾经写在纸上：

圆筒状透明杯子，半杯水。如何精确确定是半杯。

从条件入手：
1. （从条件入手的穷举/试错思维）我能对杯子做什么？翻转、平放（这个时候还没想到倾斜，思维陷阱）。
2. 分解各项条件，看看能否改变，增添、去除。
    为什么是圆筒状？为什么不是棱锥、立方体、球体？为什么不是二维图形（正方形、长方形、三角形、多边形）？为什么不是一维（绳子？——绳子上扎一个结，能确定是否扎在中点吗？）
    为什么是水？为什么不是固体（沙子？）
    为什么要透明？不透明如何？透明很关键？
    为什么是半杯？为什么不是1/3？1/4？1/3的话还能确定吗？

从结论入手：
要确定半杯水，我们必须__？
反过来，如果是半杯水，那么__？
或者，如果不是半杯水，那么就不__？

从结论入手发现无法归约的时候，我就回过头去查看从条件入手的步骤。题目中的关于标准圆柱的说法再一次引起我的注意，一闪念间我注意到其实是可以倾斜的。虽然我想不起来为什么会想到倾斜的（一开始的时候基本只会思维定势的想到倒放），但回顾思考的过程，我认为把过程明确而细致的写下来起到了一定的作用，很多的可能性描述和词语本身就有启发下意识思考的作用。也许最后发现大部分写下来的都没有用，但真正的价值就在那少部分里面了，如果不写下来，那么"那少部分"也许就不会出现。

[alai]

第1题头一回做，已经做出来了，确实如LZ所说，找到重点就OK了。
第2题觉得有点漏洞，如果寄一个unlocked box，这个box本身会不会丢？不丢的话就很好办了，不过不应该这么容易的。会丢的话，那我就还没想出来。
第3、4、5题都做过了，在很多地方都见过。
第6题也不难，留意一下奇偶性就OK了。

不过感觉上这些题的解决方法好象没什么相似之处，当然，解题捉重点就是放之四海皆准的。

xxmplus的题目也比较有意思，我认为第1题的原因是"时间是单向的"，第2题准确地说还要加一些条件："零件的标准重量是已知的，称重用的天秤是带砝码的"，否则，有些题目(象LZ的第3题)用的天秤就是可以不带砝码的。

在 08-4-10，xxmplus<xxm...@gmail.com> 写道：

[alai]

奶奶代表了千百万劳动人民的智慧。

在 08-4-10，pongba<pon...@gmail.com> 写道：

>
>
> 2008/4/10 xxmplus <xxm...@gmail.com>:
> >
> 第5题不难，小时候就知道了，那时家里还有水井，这题是奶奶教我的，把桶倾斜直至水面碰到桶口，若这时水面也能碰到桶底，那就是正好一半，关键是水无常形，但体积不变。
> >
>
> 关键是奶奶的思路呢？试错？
> 我是试错试出来的。完整的思路我曾经写在纸上：
>
> 圆筒状透明杯子，半杯水。如何精确确定是半杯。
>
> 从条件入手：
> 1. （从条件入手的穷举/试错思维）我能对杯子做什么？翻转、平放（这个时候还没想到倾斜，思维陷阱）。
> 2. 分解各项条件，看看能否改变，增添、去除。
>

> 为什么是圆筒状？为什么不是棱锥、立方体、球体？为什么不是二维图形（正方形、长方形、三角形、多边形）？为什么不是一维（绳子？----绳子上扎一个结，能确定是否扎在中点吗？）

[pongba]

2008/4/10 alai <ala...@gmail.com>:

第1题头一回做，已经做出来了，确实如LZ所说，找到重点就OK了。
第2题觉得有点漏洞，如果寄一个unlocked box，这个box本身会不会丢？不丢的话就很好办了，不过不应该这么容易的。会丢的话，那我就还没想出来。

不加锁运输的话会被偷盗。
 

第6题也不难，留意一下奇偶性就OK了。

关键是，如何注意到奇偶性？是以前做过类似的题目，联想到的？那如何联想到那个题目呢？是根据题目里面的某个词语还是某种抽象结构？如果不是联想到的，那又是如何想到的？

《How to Solve it》里面波利亚说，如果你直接告诉学生关键的一步，譬如"我们考虑..."，那么什么价值也没有。我们都有过灵光一现的时刻，但鲜有人能够追寻出灵感背后的规则不是吗

[pongba]

顺便一问，《如何求解问题：现代启发式方法》一书中那个在正方形中反弹的小球何时会返回到原来轨迹的题目，有人自己想出来过吗？

如果有，强烈请教思路:)

2008/4/10 pongba <pon...@gmail.com>:

[pongba]

2008/4/10 alai <ala...@gmail.com>:

不过感觉上这些题的解决方法好象没什么相似之处，当然，解题捉重点就是放之四海皆准的。

捉重点的方法不同。有的是演绎的、有的是归纳的，有的干脆就是穷举&试错的。这几道题目我觉得都可以用试错的思路来启发式地寻找那个"重点"。

[pongba]

补充一道题目(再次友情感谢silwile同学^_^)：

一摞大饼，其中有大有小，从上到下的大小变化并没有一定的规律，你可以这样操作这摞饼：

将从最顶上算起的一摞连续的m个饼整个拿起来翻一下，再放回去。如x1,x2,x3...xm翻过以后变成xm, xm-1,... x2, x1
m由你确定

如此操作，最后能够将整摞饼排列成从上至下为从小到大（宝塔状）吗？

2008/4/10 pongba <pon...@gmail.com>:

[alai]

第1题，我觉得直接演绎就能推出来了。第6题，说不上是什么方法，一看到要证明一定是奇数，自然而然就想到奇偶性上去了。
第2题的条件是不是要这样理解：一次运输中，如果物品是带锁的box，则可以安全到达；如果没有box或box未锁，就会所有东西(连同box本身，如果有的话)都会丢失。

在 08-4-10，pongba<pon...@gmail.com> 写道：
>
>

[alai]

用归纳法解决比较容易些。不过如果要求最优解，即翻转的次数最少，则有点麻烦。

在 08-4-10，pongba<pon...@gmail.com> 写道：

[pongba]

2008/4/10 alai <ala...@gmail.com>:

第1题，我觉得直接演绎就能推出来了。第6题，说不上是什么方法，一看到要证明一定是奇数，自然而然就想到奇偶性上去了。

第一题可以直接演绎出来？
第六题你说一看证明是奇数就想到奇偶性，那实际上还是在用既有知识，也许你做过类似的题目。我的意思是，就算我没做过类似的利用奇偶性的题目，能不能通过演绎最后发现奇偶性是关键呢？

话说回来"看到奇数想到奇偶性"的确也是一个有用的启发思路，记得中学数学中有很多这类ad hoc的启发性思路，"看到xx想到xx"，但我认为它们的一个问题就是，过于ad hoc（特殊），而不是在思维的本质层面的一般性启发思路。当然，这些思路在一些问题上是绝对少不了的，有些题目要进行归约必须要用到领域知识的，否则死都演绎不出来。但这道奇偶题其实是完全可以利用一般性思路演绎出来的。
 

第2题的条件是不是要这样理解：一次运输中，如果物品是带锁的box，则可以安全到达；如果没有box或box未锁，就会所有东西(连同box本身，如果有的话)都会丢失。

 

恩，对。

[alai]

再想了一下，很容易就可以构造出一种翻大饼的办法，最多翻2m-1次就搞定。

在 08-4-10，alai<ala...@gmail.com> 写道：

[pongba]

我感兴趣于你想出这个构造法之前的思维过程:-)

2008/4/10 alai <ala...@gmail.com>:

[westhood]

第一题
所有人除了史密斯一共有9个人，每个人的答案各不相同，每个人最多握8次手。所以这些人的握手次数必然是0-8这9个不同的数。
握手次数为8的人必然和除了他\她配偶的所有人握过手，那么他\她只可能和次数为0的人为配偶，即0，8 为一对配偶。
把和握手次数为8的人相关的握手，从每个人的握手次数中去掉，剩下的7个人 ，握手次数必然是0-6这7个不同的数。同理现在现在握手次数为0，6的，
即实际握手次数为1，7的两个人也为配偶。
同理，（2，6），（3，5） ，为另外的两对配偶。握手次数为4的人，和其它的8各人均不为配偶，那么么毕为史密斯的夫人。
所以史密斯夫人的握手次数是4 次。

[alai]

对第1题演绎一把：
1. 总共10个人，每个人不与自己握手，不与配偶握手，不与同一个人握超过一次手，所以每个人最多握8次手，最少0次；
2. Mr.Smith问其它9个人握了几次手，各人回答不一样，所以每个人的握手次数刚好为0-8次，每种不同次数有1个人；
3. 有且只有一个人握了8次手，称之为A，即A与其配偶以外的所有人都握了手；
4. 记A的配偶为a，除了A夫妇以外，所有人都至少握了1次手(和A)，所以握手0次的肯定是a；
5. 从10个人中去掉A夫妇，因为A与其余每个人握了1次手，而a没有与别人握手，所以去掉A夫妇后，其它人的握手次数为1-7(不算Mr.Smith)，再去掉他们各自与A握的那次手不算，则各人的握手次数为0-6，还是每种不同次数刚好有1个人；
6. 重复第3-5步4次，直到去掉4对夫妇，最终剩下Mr.&Mrs.Smith，这时Mrs.Smith的握手次数为0，加上4次循环中去掉的4次握手，她总共握了4次手，与每对夫妇中的某一位各握了一次。

在 08-4-10，pongba<pon...@gmail.com> 写道：
>
>

[alai]

基本上这种题目的思维还是归纳法的多。
题目要求的翻法不影响下层的饼的顺序，所以自然就想先把下层的饼排好序，即从底做起；按题目要求，最底的饼应该是最大的饼，所以就要想办法把最大的饼放在最底；要改变最底的饼，唯一的方法就是所有饼整个翻过来；要让所有饼整个翻过来后，最大的饼在最底，翻之前就要把最大的饼放在最上面；要把最大的饼放在最上面，最直接的办法就是找到这张最大的饼，将这张饼直至最上面的饼一起翻过来；所以，翻2次就可以把最大的饼放在最底；剩下的就是归纳法了。

[pongba]

2008/4/10 alai <ala...@gmail.com>:

对第1题演绎一把：
1. 总共10个人，每个人不与自己握手，不与配偶握手，不与同一个人握超过一次手，所以每个人最多握8次手，最少0次；
2. Mr.Smith问其它9个人握了几次手，各人回答不一样，所以每个人的握手次数刚好为0-8次，每种不同次数有1个人；
3. 有且只有一个人握了8次手，称之为A，即A与其配偶以外的所有人都握了手；

为什么会想到从握手8次的人入手而不是其它人呢？
 

4. 记A的配偶为a，除了A夫妇以外，所有人都至少握了1次手(和A)，所以握手0次的肯定是a；
5. 从10个人中去掉A夫妇，因为A与其余每个人握了1次手，而a没有与别人握手，所以去掉A夫妇后，其它人的握手次数为1-7(不算Mr.Smith)，再去掉他们各自与A握的那次手不算，则各人的握手次数为0-6，还是每种不同次数刚好有1个人；
6. 重复第3-5步4次，直到去掉4对夫妇，最终剩下Mr.&Mrs.Smith，这时Mrs.Smith的握手次数为0，加上4次循环中去掉的4次握手，她总共握了4次手，与每对夫妇中的某一位各握了一次。

[pongba]

2008/4/10 alai <ala...@gmail.com>:

基本上这种题目的思维还是归纳法的多。
题目要求的翻法不影响下层的饼的顺序，所以自然就想先把下层的饼排好序，即从底做起；

这里我们的思维就不一样。

你是通过对题目条件的观察（演绎？）发现这样一个性质的，即"不影响下层饼"，这一步推理（或观察）就已经不trivial了（可见对条件的观察，试着演绎出隐藏的结论非常关键:-)）。进一步推理到"应该先把下层饼放好"，这个环节同样也不是trivial的。

实际上，事后看来，严格来说，这种操作是可以"改变下层饼的顺序的"。

我和silwile都是通过对一个特例（三个饼或四个饼）进行试错式操作来观察的。

得到答案之后我又想，是不是一开始应该对结论进行分解（分治？），因为要想摞好一摞饼，一个明显的办法就是"先摞好一些，再摞好一些"，一步一步来。silwile说在思考的时候联想到汉诺塔，并且一直想要对题目进行归约，即归约到n-1的情况，这个指导性的思维肯定也是很有帮助的。

[alai]

我来贡献一题，不过也是抄来的：
A国由1000000个岛组成，岛与岛之间只能用船作为交通工具，有些岛之间有船来往，从任意一个岛都可以去到另外任一个岛，当然其中可能要换船。现在有一个警察要追捕一个逃犯，开始时他们在不同的岛上，警察和逃犯都是每天最多乘一次船，但这个逃犯还有点迷信，每个月的13日不乘船，警察则不迷信。警察每天乘船前都知道逃犯昨天在哪个岛上，但不知道他今天会去哪个岛。请证明，警察一定可以抓到逃犯(即到达同一个岛)。

在 08-4-10，pongba<pon...@gmail.com> 写道：
>
>

[pongba]

每两个岛之间都有船可以双向来往吗？

2008/4/10 alai <ala...@gmail.com>:

[xxmplus]

既然中间需要换船，应该就不是全连通的了

2008/4/10 pongba <pon...@gmail.com>:

--

[alai]

这个条件应该无所谓。就算可以双向吧。

[pongba]

如果是双向全连通的不就trivial了？等到13号，上岛抓人。

2008/4/10 alai <ala...@gmail.com>:

[alai]

没说全连通啊，应该是无向连通图。其实就算是有向图，只要满足从任意一个岛都有办法可以去到其它任一个岛，解法也是一样的。

[Xin Li]

想了一下，如果小球入射角度的正切值是有理数，应该可以使运行轨迹重合。不过还没仔细验证。

在08-4-10，pongba <pon...@gmail.com> 写道：

[sanachilleus]

应该不是全连通的，有这样一个条件： 有些岛之间有船来往，从任意一个岛都可以去到另外任一个岛，当然其中可能要换船。
注意“有些”和“可能”这样的字眼，应该是表示非全连通。

先说一下我的答案：
初始的时候警察和罪犯在两个岛上，这两个岛一定是连通的，它们之间的最短路经为n。那么警察在n天之后可以到达逃犯初始的岛上。然后沿着逃犯走过的路线
前进，于是每月13号时警察和逃犯之间的距离减少1，在最多n月之后可以追上逃犯。

[sanachilleus]

想到这样的解法是因为岛的数量特别多（恐怕出题者也搞不清当时输入了几个0吧^-^），所以应该没有特别意义，任何一个其他正整数都可以。那么，正整数
之间的共同点，恐怕就是“有限”了。所以我就希望找到一个逐步达成目的的方法。自然的，每一步都在于13号这个特殊条件。于是答案就渐渐浮出水面了。我
的解法其实有个问题，如果n很大，警察恐怕不能在有生之年完成任务……不过这个应该不是出题者的本意吧，呵呵。

[pongba]

2008/4/10 Xin Li <sunx...@gmail.com>:

想了一下，如果小球入射角度的正切值是有理数，应该可以使运行轨迹重合。不过还没仔细验证。

思路

[sanachilleus]

我在补充一系列问题，这些问题是我闲来无事自己想的，如有雷同纯属巧合。

先给几个定义：

零、数列，数列的秩：
#define 数列 有序自然数集
数列的秩为一个有序自然数集成员个数；
名称为a，秩为n的数列记为a[n]

一、单调数列，左增数列，右增数列：
对于一个数列a[n]，如果
a)对于任意0 <= j < i < n，a[i] - a[j] > 0;
b)对于任意0 <= j < i < n，a[i] - a[j]< 0;
之一成立，则称数列a[n]为单调数列；
如果a)成立，则称数列a[n]为右增单调数列，简称右增数列；
如果b)成立，则称数列a[n]为左增单调数列，简称左增数列。

二、子数列：
对于数列a[n]、b[m]，如果n >= m，且存在数列c[m]，同时满足：
a) 0 <= c[0] < c[1] < c[2] < ... < c[m - 1] < n；
b) a[c[0]] = b[0]、a[c[1]] = b[1]、a[c[2]] = b[2]、...a[c[m - 1]] = b[m -
1]；
则称数列b[m]为数列a[n]的子数列；

三、数列拆分：
如果数列a1[n1]，a2[n2]，a3[n3]，...am[nm]都是数列a[n]的子数列，且满足：
a)n1 + n2 + ... + nm = n；
b)对于任意0 < i < j <= m，0 <= p < ni，0 <= q < nj，ai[p] != aj[q]成立；
那么称a1[n1]，a2[n2]，a3[n3]，...am[nm]是数列a[n]的一个拆分。


问题：
对于

On 4月10日, 下午7时50分, sanachilleus <sanachill...@gmail.com> wrote:

[sanachilleus]

前面的定义说的很麻烦，其实理解起来很简单：
数列就是把若干个各不相同的自然数排成一行；
数列的秩就是这一行数的个数；
单调数列就是单调递增或单调递减数列；
一个数列中任意去掉几个元素，剩下的就是一个子数列；
把一个数列分成互不相交的"几份"，就是数列的一个拆分。

> > 前进，于是每月13号时警察和逃犯之间的距离减少1，在最多n月之后可以追上逃犯。- 隐藏被引用文字 -
>
> - 显示引用的文字 -

[Shao Feng]

pongba的第四题怎么才算赢？

[pongba]

谁能拿走最后一个橘子，谁赢。

On Thu, Apr 10, 2008 at 9:14 PM, Shao Feng <seve...@gmail.com> wrote:

pongba的第四题怎么才算赢？

[hayate]

12个球那个，原来一直困扰着我。呵呵

2008/4/10 pongba <pon...@gmail.com>:
> 有这样一类题目，它们的思路都有一个共性，就是在一堆条件中，有某个条件比其他条件更关键，从这个条件出发，只有有限的几种往下走的办法，通过穷尽这几种办法的尝试，答案往往就会迅速浮出水面。
> 不妨称这个启发法为"穷举/试错"启发法。
>
> 例如
> 1.
> 来自《如何求解问题，现代启发式方法》中的题：史密斯夫妇邀请另外四对夫妇就餐，已知他们每个人都不和自己握手、不和自己的配偶握手、且不和同一个人握手一次以上。在大家见面握手寒暄后，史密斯问大家握手了几次，每个人的答案都不一样。问：史密斯太太握手几次。
> 2. 来自一个pdf，Seven Puzzles You Think You Must Not Have Heard Correctly：Jan and
> Maria have fallen in love (via the internet) and Jan wishes to mail her a
> ring. Unfortunately,
> they live in the country of Kleptopia where anything sent through the mail
> will be stolen unless it is enclosed in a padlocked box. Jan and Maria each
> have plenty of padlocks, but none to which the other has a key. How can Jan
> get the ring safely into Maria's hands?
> 3. 来自网络流传：12个球有一个重量不同，3次称出。
> 4.
> 来自网络流传（以及《编程之美》）：2堆橘子，m和n个。两人轮流拿。每个人拿的时候只能从其中一堆拿（不能跨堆拿），并且可以从他选定的那堆中拿走任意多个（0~剩下的所有）。那么，有无必胜策略，先后手有关系吗？
> 5. 来自伯克利的那个网址：一个标准圆柱体无盖透明杯子，里面似乎有半杯水，要你不借助任何工具，判定它是否精确地装了半杯水。
> 6.
> 来自一本奥林匹克数学竞赛题目集：n为奇数，现罗列出1,2,...2n这2n个数，然后我每次从中任取两个数a,b，并放回|a-b|，如此操作到只剩一个数，证明这个数一定是奇数。
>
> P.S. 答案不是目的，思路才是目的。（为什么？）
> 知道更多相似题目的老大也请不吝跟贴:)
>
> BTW.
> 在穷举有限的可能性的过程中人脑很容易犯一个错误，那就是忽略了某个关键的可能性，即落入思维陷阱。所以把思维的过程细致的写下来很重要，也许在某个环节上你想当然地认为下面一步肯定是A，然而通过细查写下来的思路你发现还有一种隐蔽的可能性。如果不写下来，是很难发现的。
>

[sanachilleus]

关于方盒中小球的问题，我同意Xin Li同学的结论：
当入射角正切值为比数时小球可以回到原来的路径。
可以把正方形的盒子“展开”成一个无尽的走廊，在把走廊“展开”成无尽的广场，然后在广场上画出和初始正方形相同的正方形网格。
然后，方格内的小球运行轨迹可以映射到广场上的一条射线，P。
我们令方盒的边长为1，然后在广场上建立平面直角坐标系。我们以正方形的左上和右下两个点表示正方形,如{(0, 0), (1, 1)}
不妨设射线P的起点在点(0, 1 - y)上,并且与正方形{(0, 0), (1, 1)}的另一条边[(0, 1), (1, 1)]相交与点
(x, 1)。
可以证明（这个证明很简单，回到方盒内，利用时间回溯时小球轨迹逆转），如果存在正方形{(m, n), (m + 1, n + 1)}，使得射线P
与这个方形交于点(m, n + 1 - y)和点(m + x, n + 1)，那么小球可以回到原来的路径。
如果存在这个正方形，利用三角形的相似性，有x / (x + m) = y / (y + n)等价于x / m = y / n等价于 x /
y = m / n等价于入射角正切值为比数

ps 本来我画了一张图，看得很清楚，后来发现不会上传图片- -||请同学们按照我的描述画出坐标系，就会很清晰。

[Xin Li]

A ------------------D

|                     |

s                    |

|  \                  |

| a \                |

|     \               |

|                     |

B-------------------C

 

 

假设小球从盒子AB边上某点S开始运动，与AB边夹角为a。

要求小球的运动轨迹能够重合，则小球在经过一系列碰撞后一定能重新回到s点，且与AB的夹角仍然为a。

然后就开始画轨迹图了，首先小球与盒子下壁BC发生第一次碰撞交于s1，然后与CD发生第二次碰撞交于s2。

 

A -----------s3----D

|                 \   |

s                  s2

|  \              /   |

| a \           /    |

|     \        /      |

|       \    /        |

B------s1----------C

 

 

第一个联想到的就是延长光路（碰撞与镜面反射的类比），光线在s1处发生镜面反射，如果继续延长光路，扩展的光路会交CD'于s2'。观察s2'很容易发现s2'是s2关于BC'的镜面反射点。于是得到，在新盒子BA'D'C(ABCD关于BC的镜面发射)'中，我们得到的反射点s2'与ABCD中反射点s2是上下颠倒的。

A -----------s3----D

|                 \   |

s                  s2

|  \              /   |

| a \           /    |

|     \        /      |

|       \    /        |

B------s1----------C------------------A''

|         \           |                    |

|           \         |                    |

|             \       |                    |

|               \     |                    |

|                \    |                    |

|                  s2'                    |

|                  /  |  \                 |

A'-----------s3'---D'---s3''-----------B''

 

在s2'处做同样处理，继续延长光路得到CD'B''A''和新的碰撞点s3''。观察CD'B''A''中s3''的位置与ABCD中s3位置，发现他们既上下颠倒，同时也左右颠倒。这时得到一个想法，每经过一次水平面镜面反射(BC边)，在新盒子中得到的碰撞点与在原始盒子中该次真实碰撞点位置左右颠倒。同样，每经过一次垂直面(CD边)镜面反射，在新盒子中得到的碰撞点与在原始盒子中该次真实碰撞点位置上下颠倒。（很容易验证和证明）

 

 

我们可以无限的将光路延伸下去，最终只要光路交扩展出的某个盒子垂直面(C'''D''')于某一点s'''，s'''在最新的扩展盒子中的位置与s在ABCD中的位置完全一致，而且光路在途中经过了偶数次的水平反射和偶数次的垂直反射，那么就可以保证，小球轨迹一定会重合。

 

再画张图分析一下s'''的位置，以s和s'''为斜边做直角三角形sos'''，可以得到so的长度为2ML(盒子边长)，os'''长度为2NL(M,N为任意整数)，与s点的位置完全无关。所以，只要a的正切值为N/M(M,N为任意整数,N/M其实就是所有正有理数），就可以保证小球的运动轨迹会重合。

 

总结一下，只要考虑到向外扩展线路应该可以很容易解决掉这道题。不过结论有些出乎意料，入射角正切值要是有理数，很有意思，感谢pongba。

很容易可以扩展出长方形的版本，结论只是加入边长之比。还可以扩展一个圆形版本，如果一个小球在水平的圆形容器中运动，所有的碰撞都是无损的，那么在什么样的条件下，小球的运动轨迹会出现重合？

 

 

 

在08-4-10，pongba <pon...@gmail.com> 写道：

[pongba]

这个不得不说强！

关键就是那个光线镜像类比，太NB，佩服。我觉得常人很难把思维扩展到盒子外头的。

2008/4/10 Xin Li <sunx...@gmail.com>:

[hayate]

联想固然有用，但是也有可能被误导啊，特别是习惯了某种联想。
另外，有些题并不是从题干就可以嗅到线索的。

2008/4/10 pongba <pon...@gmail.com>:
>
>
>
> 2008/4/10 alai <ala...@gmail.com>:
>

> > 第1题，我觉得直接演绎就能推出来了。第6题，说不上是什么方法，一看到要证明一定是奇数，自然而然就想到奇偶性上去了。
>
> 第一题可以直接演绎出来？
> 第六题你说一看证明是奇数就想到奇偶性，那实际上还是在用既有知识，也许你做过类似的题目。我的意思是，就算我没做过类似的利用奇偶性的题目，能不能通过演绎最后发现奇偶性是关键呢？
>
> 话说回来"看到奇数想到奇偶性"的确也是一个有用的启发思路，记得中学数学中有很多这类ad
> hoc的启发性思路，"看到xx想到xx"，但我认为它们的一个问题就是，过于ad
> hoc（特殊），而不是在思维的本质层面的一般性启发思路。当然，这些思路在一些问题上是绝对少不了的，有些题目要进行归约必须要用到领域知识的，否则死都演绎不出来。但这道奇偶题其实是完全可以利用一般性思路演绎出来的。
>
> >
> 第2题的条件是不是要这样理解：一次运输中，如果物品是带锁的box，则可以安全到达；如果没有box或box未锁，就会所有东西(连同box本身，如果有的话)都会丢失。
> 恩，对。
>
>

[hayate]

奇偶性这个我是第一次做
我的习惯是对于这种general的题干，不妨取n等于较小的数，然后列举观察。(更像是昨天的讨论)
其中我还尝试了逆向分析，如果最后是奇数，那么可以由哪几种情况得到；如果是偶数，是由哪几种情况得出。以期比较得出不同。
另外，从开始我就坚信，每次一次变化都具有某种不变性，所以注意力一直在于寻找某种不变性。
最后，就发现奇数的个数的奇偶性是不变的。

总结，题目不明确的时候，会做很多尝试。但是这些尝试几乎都来自于原来所受的训练和所形成的联想。基本上，归纳，演绎，分析，反证，都是通常会进行的尝试。如果这样就解决了问题，就没有什么灵光一闪的感觉。
2008/4/10 hayate <haya...@gmail.com>:

[pongba]

对，基本上最常用的就是特例、观察、正向演绎、反演归约、试错、分类讨论、修改条件这些手法:)

2008/4/10 hayate <haya...@gmail.com>:

[sanachilleus]

对于Xin Li同学提出的小球在圆形容器中的扩展，我的结论是：
对于小球入射角（入射边与入射点切线的夹角）a，当存在有理数k，使得k * a = PAI时小球可以回到原来的路径。

设圆心为O，小球第一次碰撞与点A，入射角a，第二次碰撞与点B，那么三角形AOB是等腰三角形，所以第二次的入射角也是a，所以以后每次碰撞的入射角
都是a。
就是说入射角保持不变。所以小球能否回到原来的路径上就等价于小球能否碰撞同一点2次。
因为每次入射角都相同，所以相邻两次碰撞的点P、Q，角POQ都相同，都是2a。我们假定第一次碰撞的点A于圆心O所在的直线为角度为0，那么第二次为
2a或-2a，第k次为2ka或-2ka。如果第n次碰撞的点又回到A，那么存在正整数m使得 2na = 2m * PAI 或者 -2na =
2m * PAI 由于m和n都是整数，所以原命题等价于存在有理数k，使得k * a = PAI

On 4月11日, 上午12时48分, pongba <pon...@gmail.com> wrote:
> 对，基本上最常用的就是特例、观察、正向演绎、反演归约、试错、分类讨论、修改条件这些手法:)
>

> 2008/4/10 hayate <hayate...@gmail.com>:

>
>
>
>
>
> > 奇偶性这个我是第一次做
> > 我的习惯是对于这种general的题干，不妨取n等于较小的数，然后列举观察。(更像是昨天的讨论)
> > 其中我还尝试了逆向分析，如果最后是奇数，那么可以由哪几种情况得到；如果是偶数，是由哪几种情况得出。以期比较得出不同。
> > 另外，从开始我就坚信，每次一次变化都具有某种不变性，所以注意力一直在于寻找某种不变性。
> > 最后，就发现奇数的个数的奇偶性是不变的。
>

> > 总结，题目不明确的时候，会做很多尝试。但是这些尝试几乎都来自于原来所受的训练和所形成的联想。基本上，归纳，演绎，分析，反证，都是通常会进行的尝试。如果-这样就解决了问题，就没有什么灵光一闪的感觉。
> > 2008/4/10 hayate <hayate...@gmail.com>:

> > > 联想固然有用，但是也有可能被误导啊，特别是习惯了某种联想。
> > > 另外，有些题并不是从题干就可以嗅到线索的。
>
> > > 2008/4/10 pongba <pon...@gmail.com>:
>
> > > > 2008/4/10 alai <ala...@gmail.com>:
>
> > > > > 第1题，我觉得直接演绎就能推出来了。第6题，说不上是什么方法，一看到要证明一定是奇数，自然而然就想到奇偶性上去了。
>
> > > > 第一题可以直接演绎出来？
>

> > 第六题你说一看证明是奇数就想到奇偶性，那实际上还是在用既有知识，也许你做过类似的题目。我的意思是，就算我没做过类似的利用奇偶性的题目，能不能通过演绎最-后发现奇偶性是关键呢？

>
> > > > 话说回来"看到奇数想到奇偶性"的确也是一个有用的启发思路，记得中学数学中有很多这类ad
> > > > hoc的启发性思路，"看到xx想到xx"，但我认为它们的一个问题就是，过于ad
>

> > hoc（特殊），而不是在思维的本质层面的一般性启发思路。当然，这些思路在一些问题上是绝对少不了的，有些题目要进行归约必须要用到领域知识的，否则死都演绎-不出来。但这道奇偶题其实是完全可以利用一般性思路演绎出来的。
>
> > 第2题的条件是不是要这样理解：一次运输中，如果物品是带锁的box，则可以安全到达；如果没有box或box未锁，就会所有东西(连同box本身，如果有的话-)都会丢失。

> > > > 恩，对。
>
> > > > --
>
> > > > 刘未鹏(pongba)|C++的罗浮宫
> > > >http://blog.csdn.net/pongba
> > > > TopLanguage
> > > >http://groups.google.com/group/pongba
>
> --
> 刘未鹏(pongba)|C++的罗浮宫http://blog.csdn.net/pongba

> TopLanguagehttp://groups.google.com/group/pongba- 隐藏被引用文字 -
>
> - 显示引用的文字 -

[Xin Li]

 

入射角a的单位用角度表示结论可以更简洁：）

 

在08-4-11，sanachilleus <sanach...@gmail.com> 写道：

[pongba]

2008/4/10 alai <ala...@gmail.com>:

我来贡献一题，不过也是抄来的：
A国由1000000个岛组成，岛与岛之间只能用船作为交通工具，有些岛之间有船来往，从任意一个岛都可以去到另外任一个岛，当然其中可能要换船。现在有一个警察要追捕一个逃犯，开始时他们在不同的岛上，警察和逃犯都是每天最多乘一次船，但这个逃犯还有点迷信，每个月的13日不乘船，警察则不迷信。警察每天乘船前都知道逃犯昨天在哪个岛上，但不知道他今天会去哪个岛。请证明，警察一定可以抓到逃犯(即到达同一个岛)。

我想的过程大概是这样的：首先想到的是用特例来启发，假设只有4个岛（3个岛又感觉少了点），但由于不知道连通方式，如果任选一种连通方式的话很快就发现引入了额外的假设，从而得出的解并不适合原题，所以暂时把特例法搁置了。

如果从条件出发，考虑警察可能怎么走才能达到目的的话，由于第一步的可能性就有无穷多，一时想不出哪种比另一种更好（这里想到应该假定逃犯总是跟警察对着干，否则撞也可能撞上）（现在想来，其实这条思路也是行得通的。只要考虑警察的"最佳"走法，但由于可能当时脑子里想的是也许警察有某种非常聪明的走法，所以忽视了最简单的可能性）。

感觉这条路暂时似乎也行不通之后，试着从结论出发，如果警察在第n天能够抓到逃犯，那么在n-1天警察和逃犯的状态只能是"位于相邻的（一步通达）的岛上"；接着往前演绎发现可能性又敞开了，"第n-2天的状态呢？""两步相邻？"那又如何？"如何从初始配置到达这个状态呢？"本来，倒推到这个地方，答案应该就会浮现了。但当时却又没有，所以挺可惜，本应接着考虑如何从n-2状态过度到n-1状态的。

结果再次回到题目，想起来一开始的一个联想，是不是无论警察怎么走，终会有一天碰到囚犯呢？（因为警察和囚犯之间的距离是从0到1000000之间的整数，而天数是无穷的，有点像鸽笼原理的类比但其实并不是），简单感觉了一下，还是存在这样一种可能性，如果警察不注意走法的话，囚犯总是能够避开警察。于是，进而开始思考囚犯怎样才能够永远避开警察，使得他们的距离永远>1呢？注意警察和囚犯的这种对抗关系，为了能够紧盯囚犯，警察应该永远走最优路线（最短路径），注意到囚犯每次只能走一步，所以警察囚犯之间的路程这样看的话永远不会增加，同时每月13号，至少能够减一。那么，终有一天，是会递减到0的。

回想一下其实前两步的思路稍微延伸一下就可以到达答案，但还没有试遍所有可能性就过早放弃了。

P.S. 如果这个题目改为33个岛，也许更有迷惑性。100000个岛的条件很明显的隐含了"岛的数目无关"这个假设。

[sanachilleus]

看到Xin Li 同学提出的关于长方形盒子和圆形盒子的扩展，我又想到了两个更邪恶的扩展：在什么情况下，菱形盒子内的小球可以回到原来的路径？椭圆
形的盒子呢？

On 4月11日, 上午11时06分, pongba <pon...@gmail.com> wrote:
> 2008/4/10 alai <ala...@gmail.com>:
>
> > 我来贡献一题，不过也是抄来的：
>

> > A国由1000000个岛组成，岛与岛之间只能用船作为交通工具，有些岛之间有船来往，从任意一个岛都可以去到另外任一个岛，当然其中可能要换船。现在有一个警-察要追捕一个逃犯，开始时他们在不同的岛上，警察和逃犯都是每天最多乘一次船，但这个逃犯还有点迷信，每个月的13日不乘船，警察则不迷信。警察每天乘船前都知-道逃犯昨天在哪个岛上，但不知道他今天会去哪个岛。请证明，警察一定可以抓到逃犯(即到达同一个岛)。
>
> 我想的过程大概是这样的：首先想到的是用特例来启发，假设只有4个岛（3个岛又感觉少了点），但由于不知道连通方式，如果任选一种连通方式的话很快就发现引入了-额外的假设，从而得出的解并不适合原题，所以暂时把特例法搁置了。
>
> 如果从条件出发，考虑警察可能怎么走才能达到目的的话，由于第一步的可能性就有无穷多，一时想不出哪种比另一种更好（这里想到应该假定逃犯总是跟警察对着干，否-则撞也可能撞上）（现在想来，其实这条思路也是行得通的。只要考虑警察的"最佳"走法，但由于可能当时脑子里想的是也许警察有某种非常聪明的走法，所以忽视了最-简单的可能性）。
>
> 感觉这条路暂时似乎也行不通之后，试着从结论出发，如果警察在第n天能够抓到逃犯，那么在n-1天警察和逃犯的状态只能是"位于相邻的（一步通达）的岛上"；接-着往前演绎发现可能性又敞开了，"第n-2天的状态呢？""两步相邻？"那又如何？"如何从初始配置到达这个状态呢？"本来，倒推到这个地方，答案应该就会浮现-了。但当时却又没有，所以挺可惜，本应接着考虑如何从n-2状态过度到n-1状态的。
>
> 结果再次回到题目，想起来一开始的一个联想，是不是无论警察怎么走，终会有一天碰到囚犯呢？（因为警察和囚犯之间的距离是从0到1000000之间的整数，而天-数是无穷的，有点像鸽笼原理的类比但其实并不是），简单感觉了一下，还是存在这样一种可能性，如果警察不注意走法的话，囚犯总是能够避开警察。于是，进而开始思-考囚犯怎样才能够永远避开警察，使得他们的距离永远>1呢？注意警察和囚犯的这种对抗关系，为了能够紧盯囚犯，警察应该永远走最优路线（最短路径），注意到囚犯-每次只能走一步，所以警察囚犯之间的路程这样看的话永远不会增加，同时每月13号，至少能够减一。那么，终有一天，是会递减到0的。

[sanachilleus]

我也提个问题，这个问题是我由DND创建角色想到的：

4d6去掉最小值后求和，那么和的期望是多少？

推广：
M个独立的均匀分布于1到X的随机整数，去掉其中最小的N个，对剩下的M - N个求和。问和的期望是多少。

On 4月11日, 上午11时57分, sanachilleus <sanachill...@gmail.com> wrote:
> 看到Xin Li 同学提出的关于长方形盒子和圆形盒子的扩展，我又想到了两个更邪恶的扩展：在什么情况下，菱形盒子内的小球可以回到原来的路径？椭圆
> 形的盒子呢？
>
> On 4月11日, 上午11时06分, pongba <pon...@gmail.com> wrote:
>
>
>
> > 2008/4/10 alai <ala...@gmail.com>:
>
> > > 我来贡献一题，不过也是抄来的：
>

> > > A国由1000000个岛组成，岛与岛之间只能用船作为交通工具，有些岛之间有船来往，从任意一个岛都可以去到另外任一个岛，当然其中可能要换船。现在有一个警--察要追捕一个逃犯，开始时他们在不同的岛上，警察和逃犯都是每天最多乘一次船，但这个逃犯还有点迷信，每个月的13日不乘船，警察则不迷信。警察每天乘船前都-知-道逃犯昨天在哪个岛上，但不知道他今天会去哪个岛。请证明，警察一定可以抓到逃犯(即到达同一个岛)。
>
> > 我想的过程大概是这样的：首先想到的是用特例来启发，假设只有4个岛（3个岛又感觉少了点），但由于不知道连通方式，如果任选一种连通方式的话很快就发现引入了--额外的假设，从而得出的解并不适合原题，所以暂时把特例法搁置了。
>
> > 如果从条件出发，考虑警察可能怎么走才能达到目的的话，由于第一步的可能性就有无穷多，一时想不出哪种比另一种更好（这里想到应该假定逃犯总是跟警察对着干，否--则撞也可能撞上）（现在想来，其实这条思路也是行得通的。只要考虑警察的"最佳"走法，但由于可能当时脑子里想的是也许警察有某种非常聪明的走法，所以忽视了-最-简单的可能性）。
>
> > 感觉这条路暂时似乎也行不通之后，试着从结论出发，如果警察在第n天能够抓到逃犯，那么在n-1天警察和逃犯的状态只能是"位于相邻的（一步通达）的岛上"；接--着往前演绎发现可能性又敞开了，"第n-2天的状态呢？""两步相邻？"那又如何？"如何从初始配置到达这个状态呢？"本来，倒推到这个地方，答案应该就会浮-现-了。但当时却又没有，所以挺可惜，本应接着考虑如何从n-2状态过度到n-1状态的。
>
> > 结果再次回到题目，想起来一开始的一个联想，是不是无论警察怎么走，终会有一天碰到囚犯呢？（因为警察和囚犯之间的距离是从0到1000000之间的整数，而天--数是无穷的，有点像鸽笼原理的类比但其实并不是），简单感觉了一下，还是存在这样一种可能性，如果警察不注意走法的话，囚犯总是能够避开警察。于是，进而开始-思-考囚犯怎样才能够永远避开警察，使得他们的距离永远>1呢？注意警察和囚犯的这种对抗关系，为了能够紧盯囚犯，警察应该永远走最优路线（最短路径），注意到-囚犯-每次只能走一步，所以警察囚犯之间的路程这样看的话永远不会增加，同时每月13号，至少能够减一。那么，终有一天，是会递减到0的。

>
> > 回想一下其实前两步的思路稍微延伸一下就可以到达答案，但还没有试遍所有可能性就过早放弃了。
>
> > P.S. 如果这个题目改为33个岛，也许更有迷惑性。100000个岛的条件很明显的隐含了"岛的数目无关"这个假设。
>
> > --
> > 刘未鹏(pongba)|C++的罗浮宫http://blog.csdn.net/pongba

[pongba]

2008/4/11 sanachilleus <sanach...@gmail.com>:

我也提个问题，这个问题是我由DND创建角色想到的：

4d6去掉最小值后求和，那么和的期望是多少？

推广：
M个独立的均匀分布于1到X的随机整数，去掉其中最小的N个，对剩下的M - N个求和。问和的期望是多少。

4d6是什么意思？

[pongba]

刚才在看陶哲轩的《Solving Mathematic Problems》（很好的书），在他提到"略去前提条件"启发法的时候，忽然联想到这个题目完全是可以通过这种方法启发出答案的。

我们忽略"逃犯每月13号不乘船"这个条件；那么警察似乎永远就别想抓到逃犯了，为什么呢？我想到这里就很容易想到"哦，原来警察每接近一步，逃犯也都逃开一步"。那么再加上这个条件有什么不同呢？答案也就呼之欲出了。

2008/4/11 pongba <pon...@gmail.com>:

[pongba]

再补充一题，我觉得也属于这一类：

You are wearing a blindfold and thick gloves. An infinite number of quarters are laid out before you on a table of infinite area. Someone tells you that 20 of these quarters are tails and the rest are heads. He says that if you can split the quarters into 2 piles where the number of tails quarters is the same in both piles, then you win all of the quarters. You are allowed to move the quarters and to flip them over, but you can never tell what state a quarter is currently in (the blindfold prevents you from seeing, and the gloves prevent you from feeling which side is heads or tails). How do you partition the quarters so that you can win them all?

来源：http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#infiniteQuarterSeq

2008/4/10 pongba <pon...@gmail.com>:

--
刘未鹏(pongba)|C++的罗浮宫
http://blog.csdn.net/pongba
TopLanguage
http://groups.google.com/group/pongba

[alai]

我猜是6中取4吧？
问一下sanachilleus，M个整数允许重复吗？

在 08-4-11，pongba<pon...@gmail.com> 写道：

[sanachilleus]

4d6指 一个6面色子，掷4次。

M个数允许重复，因为它们是独立的随机数。

On 4月11日, 下午2时06分, alai <ala...@gmail.com> wrote:
> 我猜是6中取4吧？
> 问一下sanachilleus，M个整数允许重复吗？
>
> 在 08-4-11，pongba<pon...@gmail.com> 写道：
>
>
>
>
>

> > 2008/4/11 sanachilleus <sanachill...@gmail.com>:

> > > 我也提个问题，这个问题是我由DND创建角色想到的：
>
> > > 4d6去掉最小值后求和，那么和的期望是多少？
>
> > > 推广：
> > > M个独立的均匀分布于1到X的随机整数，去掉其中最小的N个，对剩下的M - N个求和。问和的期望是多少。
>
> > 4d6是什么意思？
>
> > --
> > 刘未鹏(pongba)|C++的罗浮宫
> >http://blog.csdn.net/pongba
> > TopLanguage
>

[sanachilleus]

pongba 的那个分硬币的题，如果允许我翻动硬币的话，我的结论是这样的：

任意取出20枚，全部翻到反面，堆成一堆，就好了。

如果不能翻动，实在想不出有什么办法。


因为题目中我被剥夺了所有感知能力，所以任何选取硬币的行为都是随机的。无论怎样划分，都无法知道哪一堆里有多少硬币。只知道一堆有X个，另一堆有
20 - X个。
于是我就想通过翻动硬币改变反面向上硬币的数目。然后问题就简单了。如果只有一个反面的硬币，大家都知道该怎么办，2个、3个...20个，问题是一样
的。

> > - 显示引用的文字 -- 隐藏被引用文字 -
>
> - 显示引用的文字 -

[Du Lei]

我就想说4d6这种黑话不是圈内人肯定看不懂……

2008/4/11 sanachilleus <sanach...@gmail.com>:

[pongba]

2008/4/11 sanachilleus <sanach...@gmail.com>:

pongba  的那个分硬币的题，如果允许我翻动硬币的话，我的结论是这样的：

任意取出20枚，全部翻到反面，堆成一堆，就好了。

正解。可以翻的，题目里面说了的，题目里面还有一个迷惑变量，就是硬币数目无限。关键是想到可以拿出有限个。。。

[pongba]

2008/4/11 sanachilleus <sanach...@gmail.com>:

4d6指 一个6面色子，掷4次。

M个数允许重复，因为它们是独立的随机数。

应该是接近12，我算出来是12.05（精确到小数点后2位）。
我算的方法是将整个和的期望3.5*4，减去最小点数的期望，后者可以通过定义算出来：

6*P(有一个是6，其余>=6) + 5*P(有一个是5，其余>=5) + ... +1*P(有一个是1，其余>=1)

[alai]

从1-X中重复随机选择M次，去掉最小的N个数，求剩下的M-N个数的和的期望值。
对于N=1的情况比较好算，应该是：
(1+X)/2*M - (X^M+(X-1)^M+...+2^M+1^M)/X^M

对于X=6，M=4，即：
(1+6)/2*4 - (6^4+5^4+4^4+3^4+2^4+1^4)/6^4 ≈ 14 - 1.7554 = 12.2446

推导的方法与pongba的相同，对于N>1的情况，虽然原理相同，但算不出来公式。

在 08-4-15，pongba<pon...@gmail.com> 写道：

[pongba]

2008/4/15 alai <ala...@gmail.com>:

从1-X中重复随机选择M次，去掉最小的N个数，求剩下的M-N个数的和的期望值。
对于N=1的情况比较好算，应该是：
(1+X)/2*M - (X^M+(X-1)^M+...+2^M+1^M)/X^M

对于X=6，M=4，即：
(1+6)/2*4 - (6^4+5^4+4^4+3^4+2^4+1^4)/6^4 ≈ 14 - 1.7554 = 12.2446

(6^4+5^4+4^4+3^4+2^4+1^4)/6^4
这个式子的含义是什么？

从你的计算公式，你应该是在算Xmin这个随机变量的数学期望。
Xmin的所有可能的值是1,2,3,4,5,6。每个值都有一个概率。根据数学期望的公式：

E(Xmin) = 6*P(Xmin==6) + 5*P(Xmin==5) + ... + 1*P(Xmin==1)

[alai]

正是计算每个可能值的概率，再乘以可能值，相加，进行简化后的结果。
所有排列的总数为X^M个，这很简单吧。那么最小值为1的排列总数有多少个？等于所有排列的总数，减去最小值不是1的排列总数。最小值不是1的排列，其实就是不含1的排列，即从2-X中重复取M次的排列总数，即(X-1)^M个。所以，最小值为1的排列总数为(X^M
- (X-1)^M)个，概率为(X^M - (X-1)^M)/X^M。
同样，最小值为2的排列总数，就是((X-1)^M - (X-2)^M)个，概率为((X-1)^M - (X-2)^M))/X^M。依此类推，最小值的期望值为：
1*(X^M - (X-1)^M))/X^M + 2*((X-1)^M - (X-2)^M))/X^M + ... + X*(1^M - 0^M))/X^M
= (X^M+(X-1)^M+...+2^M+1^M))/X^M

在 08-4-15，pongba<pon...@gmail.com> 写道：
>
>

[pongba]

2008/4/15 alai <ala...@gmail.com>:

正是计算每个可能值的概率，再乘以可能值，相加，进行简化后的结果。
所有排列的总数为X^M个，这很简单吧。那么最小值为1的排列总数有多少个？等于所有排列的总数，减去最小值不是1的排列总数。最小值不是1的排列，其实就是不含1的排列，即从2-X中重复取M次的排列总数，即(X-1)^M个。所以，最小值为1的排列总数为(X^M
- (X-1)^M)个，概率为(X^M - (X-1)^M)/X^M。
同样，最小值为2的排列总数，就是((X-1)^M - (X-2)^M)个，概率为((X-1)^M - (X-2)^M))/X^M。依此类推，最小值的期望值为：
1*(X^M - (X-1)^M))/X^M + 2*((X-1)^M - (X-2)^M))/X^M + ... + X*(1^M - 0^M))/X^M

= (X^M+(X-1)^M+...+2^M+1^M))/X^M

恩，你是对的。并且我刚才算错了，吃饭的时候用了另一种计算方法发现和你的结果是一样的，和计算机的结果也是一样的。

关键是怎样计算最小值为u的概率，我原先用的是：P(四个数中有一个u)*P(其余三个都大于等于u |四个数中有一个u)，但结果12.05与计算机模拟的的不吻合。
另一个算法是P(四个数都大于等于u)*P(其中至少有一个数等于u |四个数都大于等于u)，这个算出来和你的结果是一致的。

还没想明白第一种计算方法哪里出了问题。概率的计算最容易有微妙的错误。

想起一个经典的概率问题：你参加一个有奖竞猜活动，主持人在台上放三扇门，其中只有一扇背后是轿车，其它两扇是绵羊。首先你选中一扇门，然后主持人打开剩下两扇门中的一扇背后是绵羊的门，这时你有机会改变自己的选择，你改变选择会对中奖几率有影响吗？

[pongba]

2008/4/15 pongba <pon...@gmail.com>:

2008/4/15 alai <ala...@gmail.com>:

正是计算每个可能值的概率，再乘以可能值，相加，进行简化后的结果。
所有排列的总数为X^M个，这很简单吧。那么最小值为1的排列总数有多少个？等于所有排列的总数，减去最小值不是1的排列总数。最小值不是1的排列，其实就是不含1的排列，即从2-X中重复取M次的排列总数，即(X-1)^M个。所以，最小值为1的排列总数为(X^M
- (X-1)^M)个，概率为(X^M - (X-1)^M)/X^M。
同样，最小值为2的排列总数，就是((X-1)^M - (X-2)^M)个，概率为((X-1)^M - (X-2)^M))/X^M。依此类推，最小值的期望值为：
1*(X^M - (X-1)^M))/X^M + 2*((X-1)^M - (X-2)^M))/X^M + ... + X*(1^M - 0^M))/X^M

= (X^M+(X-1)^M+...+2^M+1^M))/X^M

恩，你是对的。并且我刚才算错了，吃饭的时候用了另一种计算方法发现和你的结果是一样的，和计算机的结果也是一样的。

关键是怎样计算最小值为u的概率，我原先用的是：P(四个数中有一个u)*P(其余三个都大于等于u |四个数中有一个u)，但结果12.05与计算机模拟的的不吻合。
另一个算法是P(四个数都大于等于u)*P(其中至少有一个数等于u |四个数都大于等于u)，这个算出来和你的结果是一致的。

其实这后一个方法和你的方法是完全一样的。

[alai]

有奖竞猜这题的确很经典，经典就经典在答案与很多人的直觉相反。虽然我知道如何算出答案，但还是弄不明白为什么它会与直觉相反。

在 08-4-15，pongba<pon...@gmail.com> 写道：
>
>

[kkyy]

郁闷，貌似发错了，发到你邮箱里去了，不想再重新打字了，麻烦把发到你邮箱里的内容贴到这后面。。。。。3q

On 4月15日, 下午6时04分, pongba <pon...@gmail.com> wrote:
> 2008/4/15 alai <ala...@gmail.com>:
>
> > 正是计算每个可能值的概率，再乘以可能值，相加，进行简化后的结果。
>

> > 所有排列的总数为X^M个，这很简单吧。那么最小值为1的排列总数有多少个？等于所有排列的总数，减去最小值不是1的排列总数。最小值不是1的排列，其实就是不-含1的排列，即从2-X中重复取M次的排列总数，即(X-1)^M个。所以，最小值为1的排列总数为(X^M

> > - (X-1)^M)个，概率为(X^M - (X-1)^M)/X^M。
> > 同样，最小值为2的排列总数，就是((X-1)^M - (X-2)^M)个，概率为((X-1)^M -
> > (X-2)^M))/X^M。依此类推，最小值的期望值为：
> > 1*(X^M - (X-1)^M))/X^M + 2*((X-1)^M - (X-2)^M))/X^M + ... + X*(1^M -
> > 0^M))/X^M
> > = (X^M+(X-1)^M+...+2^M+1^M))/X^M
>
> 恩，你是对的。并且我刚才算错了，吃饭的时候用了另一种计算方法发现和你的结果是一样的，和计算机的结果也是一样的。
>
> 关键是怎样计算最小值为u的概率，我原先用的是：P(四个数中有一个u)*P(其余三个都大于等于u
> |四个数中有一个u)，但结果12.05与计算机模拟的的不吻合。
> 另一个算法是P(四个数都大于等于u)*P(其中至少有一个数等于u |四个数都大于等于u)，这个算出来和你的结果是一致的。
>
> 还没想明白第一种计算方法哪里出了问题。概率的计算最容易有微妙的错误。
>

> 想起一个经典的概率问题：你参加一个有奖竞猜活动，主持人在台上放三扇门，其中只有一扇背后是轿车，其它两扇是绵羊。首先你选中一扇门，然后主持人打开剩下两扇-门中的一扇背后是绵羊的门，这时你有机会改变自己的选择，你改变选择会对中奖几率有影响吗？

[seawolf]

我的思维过程是这样的：
1：找个最简单的实例，试试两个饼的情况
2：从两个饼过渡到3个饼，发现把最大那个翻到最低下，就变成了两个饼的问题
3：用归纳法，n-1个饼和n个饼之间存在递推关系，把最大的饼翻到最下面，最多只要两次
4：翻n个饼最多需要2*（n-2）+ 1次

pongba 写道：
> �Ҹ���Ȥ�����������취֮ǰ��˼ά���:-)
>
> 2008/4/10 alai <ala...@gmail.com>:
>
> > ������һ�£������׾Ϳ��Թ����һ�ַ����İ취����෭2m-1�ξ͸㶨��
> >
> >
> > �� 08-4-10��alai<ala...@gmail.com> д�#�
> > > �ù��ɷ����Ƚ�����Щ���������Ҫ�����Ž⣬����ת�Ĵ������٣����е��鷳��
> > >
> > > �� 08-4-10��pongba<pon...@gmail.com> д�#�
> > > > ����һ����Ŀ(�ٴ������лsilwileͬѧ^_^)��
> > > >
> > > > һ���������д���С�����ϵ��µĴ�С�仯��û��һ���Ĺ��ɣ������������������
> > > >
> > > > ������������һ��l���m����������4��һ�£��ٷŻ�ȥ����x1,x2,x3...xm�����Ժ���xm,
> > > > xm-1,... x2, x1
> > > > m����ȷ��
> > > >
> > > > ��˲�������ܹ�����������гɴ�������Ϊ��С���󣨱���״����
> > > >
> > > > 2008/4/10 pongba <pon...@gmail.com>:
> > > >
> > > > >
> > > >
> > ������һ����Ŀ�����ǵ�˼·����һ���ԣ�������һ������У���ij����������������ؼ�����������ֻ�����޵ļ��������ߵİ취��ͨ����⼸�ְ취�ij��ԣ�������ͻ�Ѹ�ٸ���ˮ�档
> > > > > ���s�������Ϊ"���/�Դ�"�����
> > > > >
> > > > > ����
> > > > > 1.
> > > >
> > 4�ԡ����������⣬�ִ���ʽ�������е��⣺ʷ��˹�����������ĶԷ򸾾Ͳͣ���֪����ÿ���˶������Լ����֡������Լ�����ż���֡��Ҳ���ͬһ��������һ�����ϡ��ڴ�Ҽ������ֺ��Ѻ�ʷ��˹�ʴ�������˼��Σ�ÿ���˵Ĵ𰸶���һ���ʣ�ʷ��˹̫̫���ּ��Ρ�
> > > > > 2. 4��һ��pdf��Seven Puzzles You Think You Must Not Have Heard

> > Correctly��Jan
> > > > and Maria have fallen in love (via the internet) and Jan wishes to
> > mail her
> > > > a ring. Unfortunately,
> > > > > they live in the country of Kleptopia where anything sent through
> > the mail
> > > > will be stolen unless it is enclosed in a padlocked box. Jan and Maria
> > each
> > > > have plenty of padlocks, but none to which the other has a key. How
> > can Jan
> > > > get the ring safely into Maria's hands?

> > > > > 3. 4���������12������һ���� ��ͬ��3�γƳ�
> > > > > 4.
> > > >
> > 4����������Լ������֮�!�����2�����ӣ�m��n��}�������á�ÿ�����õ�ʱ��ֻ�ܴ�����һ���ã����ܿ���ã������ҿ��Դ���ѡ�����Ƕ�������������0~ʣ�µ����У�����ô�����ޱ�ʤ���ԣ��Ⱥ����й�ϵ��
> > > > > 5.
> > > > 4�Բ�������Ǹ���ַ��һ���׼Բ�����޸�͸���ӣ������ƺ��а뱭ˮ��Ҫ�㲻�����κι��ߣ��ж����Ƿ�ȷ��װ�˰뱭ˮ��
> > > > > 6.
> > > >
> > 4��һ������ƥ����ѧ������Ŀ����nΪ���������г�1,2,...2n��2n����Ȼ����ÿ�δ�����ȡ}����a,b�����Ż�|a-b|����˲���ֻʣһ����֤�������һ��������
> > > > >
> > > > > P.S. �𰸲���Ŀ�ģ�˼·����Ŀ�ġ���Ϊʲô����
> > > > > ֪�8��������Ŀ���ϴ�Ҳ�벻�߸���:)
> > > > >
> > > > > BTW.
> > > >
> > ��������޵Ŀ����ԵĹ�������Ժ����׷�һ������Ǿ��Ǻ�����ij��ؼ�Ŀ����ԣ�������˼ά���塣���԰�˼ά�Ĺ��ϸ�µ�д��4����Ҫ��Ҳ����ij��������뵱Ȼ����Ϊ����һ���϶���A��Ȼ��ͨ��ϸ��д��4��˼·�㷢�ֻ���һ�����εĿ����ԡ����д��4���Ǻ��ѷ��ֵġ�
> > > > >
> > > > > --
> > > > > ��δ��(pongba)|C++���޸���

> > > > > http://blog.csdn.net/pongba
> > > > > TopLanguage
> > > > > http://groups.google.com/group/pongba
> > > >
> > > >
> > > >

> > > > --
> > > > ��δ��(pongba)|C++���޸���

> > > > http://blog.csdn.net/pongba
> > > > TopLanguage
> > > > http://groups.google.com/group/pongba
> > > > > >
> > > >
> > >
> >
> > >
> >
>
>

> --
> ��δ��(pongba)|C++���޸���

[Uneeda]

xxm+ 的零件题目：

把这十堆零件编号1-10，并且从中取出相应的零件个数，如一号堆就取1个 10号堆就取10个。我先把这个问题化简，就是假设正品零件是10克，这
样次品就为9克。
这样把取出的一堆零件拿去称，看尾数：如果是2的话就证明是8*9=72，即在8号堆；是8的话就是2*9=18,2号堆。

现在把这个多余的假设去掉，总量就是n和n-1，接着继续用脚指头想就可以了。

On 4月10日, 下午1时34分, xxmplus <xxmp...@gmail.com> wrote:

> 2）有十堆零件，其中有一堆是次品，比正品的零件轻了1克，要求只能称一次，就把那堆次品找出来。

[Uneeda]

[Justin L]

我最后形成的解答也是这样，把最大的饼翻到最下面就可以了。
思考过程是这样的：题目的方法是整个一块翻，所以我考虑这个里面的限制条件太多了，因此考虑能否求得一个简单的方案。例如，如果我能够通过题目所给出的
方法，能够做到将任意两层的饼调换位置（推导出来的方法A），那么就可以通过推导出来的方法来完成题目的要求了。后来发现A这个方法有点复杂，似乎有更
简单的方法，A方法通过两次翻转，除了调换了两个饼的位置，还打乱了其他饼的位置。因此又考虑有没有一个方法，调换位置后，不打乱其他饼的位置呢，于是
我想到了插入排序。
最后，决定每次都把最大的饼调换到最下面即可。


On 4月10日, 下午2时53分, alai <ala...@gmail.com> wrote:
> 基本上这种题目的思维还是归纳法的多。
> 题目要求的翻法不影响下层的饼的顺序，所以自然就想先把下层的饼排好序，即从底做起；按题目要求，最底的饼应该是最大的饼，所以就要想办法把最大的饼放在最底；要改变最底的饼，唯一的方法就是所有饼整个翻过来；要让所有饼整个翻过来后，最大的饼在最底，翻之前就要把最大的饼放在最上面；要把最大的饼放在最上面，最直接的办法就是找到这张最大的饼，将这张饼直至最上面的饼一起翻过来；所以，翻2次就可以把最大的饼放在最底；剩下的就是归纳法了。
>

[dailiangren]

我以前打台球的时候曾经想过，我能不能找到一种情形，让球的轨迹通过桌面上每个点呢？
后来就用类似的方法发觉根本是不肯能的，就是可数与不可数的区别。

On Apr 10, 10:15 pm, pongba <pon...@gmail.com> wrote:
> 这个不得不说强！
>
> 关键就是那个光线镜像类比，太NB，佩服。我觉得常人很难把思维扩展到盒子外头的。
>
> 2008/4/10 Xin Li <sunxyl...@gmail.com>:
>
>
>
> > A ------------------D
> > | |
> > s |
> > | \ |
> > | a \ |
> > | \ |
> > | |
> > B-------------------C
>
> > 假设小球从盒子AB边上某点S开始运动，与AB边夹角为a。
> > 要求小球的运动轨迹能够重合，则小球在经过一系列碰撞后一定能重新回到s点，且与AB的夹角仍然为a。
> > 然后就开始画轨迹图了，首先小球与盒子下壁BC发生第一次碰撞交于s1，然后与CD发生第二次碰撞交于s2。
>
> > A -----------s3----D
> > | \ |
> > s s2
> > | \ / |
> > | a \ / |
> > | \ / |
> > | \ / |
> > B------s1----------C
>
> > 第一个联想到的就是延长光路（碰撞与镜面反射的类比），光线在s1处发生镜面反射，如果继续延长光路，扩展的光路会交CD'于s2'。观察s2'很容易发现s2'是s2关于BC'的镜面反射点。于是得到，在新盒子BA'D'C(ABCD关于BC的镜面发射)'中，我们得到的反射点s2'与ABCD中反射点s2是上下颠倒的。
> > A -----------s3----D
> > | \ |
> > s s2
> > | \ / |
> > | a \ / |
> > | \ / |
> > | \ / |
> > B------s1----------C------------------A''
> > | \ | |
> > | \ | |
> > | \ | |
> > | \ | |
> > | \ | |
> > | s2' |
> > | / | \ |
> > A'-----------s3'---D'---s3''-----------B''
>
> > 在s2'处做同样处理，继续延长光路得到CD'B''A''和新的碰撞点s3''。观察CD'B''A''中s3''的位置与ABCD中s3位置，发现他们既上下颠倒，同时也左右颠倒。这时得到一个想法，每经过一次水平面镜面反射(BC边)，在新盒子中得到的碰撞点与在原始盒子中该次真实碰撞点位置左右颠倒。同样，每经过一次垂直面(CD边)镜面反射，在新盒子中得到的碰撞点与在原始盒子中该次真实碰撞点位置上下颠倒。（很容易验证和证明）
>
> > 我们可以无限的将光路延伸下去，最终只要光路交扩展出的某个盒子垂直面(C'''D''')于某一点s'''，s'''在最新的扩展盒子中的位置与s在ABCD中的位置完全一致，而且光路在途中经过了偶数次的水平反射和偶数次的垂直反射，那么就可以保证，小球轨迹一定会重合。
>
> > 再画张图分析一下s'''的位置，以s和s'''为斜边做直角三角形sos'''，可以得到so的长度为2ML(盒子边长)，os'''长度为2NL(M,N为任意整数)，与s点的位置完全无关。所以，只要a的正切值为N/M(M,N为任意整数,N/M其实就是所有正有理数），就可以保证小球的运动轨迹会重合。
>
> > 总结一下，只要考虑到向外扩展线路应该可以很容易解决掉这道题。不过结论有些出乎意料，入射角正切值要是有理数，很有意思，感谢pongba。
>
> > 很容易可以扩展出长方形的版本，结论只是加入边长之比。还可以扩展一个圆形版本，如果一个小球在水平的圆形容器中运动，所有的碰撞都是无损的，那么在什么样的条件下，小球的运动轨迹会出现重合？
>
> > 在08-4-10，pongba <pon...@gmail.com> 写道：
>
> > > 2008/4/10 Xin Li <sunxyl...@gmail.com>:
>
> > > > 想了一下，如果小球入射角度的正切值是有理数，应该可以使运行轨迹重合。不过还没仔细验证。
>
> > > 思路
>
> > > --
> > > 刘未鹏(pongba)|C++的罗浮宫

> > >http://blog.csdn.net/pongba
> > > TopLanguage
> > >http://groups.google.com/group/pongba> >
>
> --